[LeetCode By Go 108]438. Find All Anagrams in a String

문제 의 통과 율 이 점점 낮 아 지고 문제 가 점점 길 어 지 며 문제 의 뜻 을 이해 하기 어렵 습 니 다. 경계 문제, 최적화 문제 가 중첩 되 어 문제 풀이 시간 이 크게 증가 합 니 다. 제 목표 인 기술 데이터 구조 와 알고리즘 을 신속하게 복습 하 는 데 큰 지장 이 있 습 니 다!이미 백 여 문 제 를 썼 으 니 맞 춤 형 문 제 를 풀 때 가 되 었 다.현재 다음 과 같은 측면 에서 목적 성 있 게 문 제 를 풀 계획 이다. 데이터 구조:

비트 조작

배열

링크

이 진 트 리 알고리즘:

폭력 법

탐욕 법

동태 계획

가방 문제

포장 문제

우선 링크, 이 진 트 리, 동적 계획 등 몇 가지 문제 에 대해 연습 을 강화 합 니 다.
제목.
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
문제 풀이 의 사고 방향.
s 에서 모든 p 의 anagrams 시작 위 치 를 찾 습 니 다.
해법
비교적 거 친 해법 은 s 를 옮 겨 다 니 며 s 에서 p 와 같은 긴 하위 문자열 s1 을 캡 처 한 다음 에 s1 과 p 가 anagrams 인지 비교 하 는 것 이다.s1 을 캡 처 하려 면 s 를 옮 겨 다 녀 야 합 니 다. 매번 캡 처 와 p 등 긴 하위 문자열 s1, 시간 복잡 도 O (n - p + 1) p = O (np) 는 anagrams 가 s1 과 p 를 비교 하 는 지 여 부 를 판단 하 는 것 은 각 문자 가 나타 난 횟수 가 같 는 지 비교 하 는 것 입 니 다. s1 각 문자 가 나타 난 횟수 를 map 에 넣 고 p 를 옮 겨 다 녀 야 합 니 다. 만약 p 에 문자 가 map 에 나타 나 지 않 았 다 면 anagrams 가 아니 라 는 것 을 설명 합 니 다.만약 에 나타 나 면 map 에서 문자 의 값 을 1 로 줄 이 고 map 의 각 값 이 0 인지 아 닌 지 를 최종 적 으로 판단 합 니 다. 0 이 아 닌 것 이 있 으 면 anagrams 가 아니 라 anagrams 임 을 설명 합 니 다. 그렇지 않 으 면 anagrams 입 니 다.시간 복잡 도 는 O (p + p) = O (p) 이다.총 시간 복잡 도 O (n * p2) 와 같은 해법 은 시간 초과 로 이 어 질 수 있다.
해법
s1 에 p - 2 개의 수가 겹 치 는 것 을 감안 하여 s1 이 뒤로 이동 할 때 뒤의 문자 가 나타 나 는 횟수 를 늘 리 고 앞의 문자 가 나타 나 는 횟수 를 줄 이 며 p 의 문 자 를 pMap 에 넣 을 수 있 습 니 다. sMap 에 나타 난 문 자 를 만나면 문자 가 나타 나 는 개 수 를 직접 판단 할 수 있 습 니 다. 횟수 가 다 르 면 anagrams 가 아 닙 니 다.같 으 면 sMap 의 대응 치 를 0 으로 설정 합 니 다. 옮 겨 다 닌 후 모든 sMap 의 값 이 0 이면 anagrams 입 니 다. 그렇지 않 으 면 anagrams 가 아 닙 니 다.시간 복잡 도 O (1) 총 시간 복잡 도 O (n)
코드
findAnagrams.go

package _438_Find_All_Anagrams_in_a_String

import "fmt"

func FindAnagrams(s string, p string) []int {
    lenP := len(p)
    var ret []int
    lenS := len(s)
    if lenS < lenP {
        return []int{}
    }

    var charMap map[byte]int
    charMap = make(map[byte]int)
    for i := 0; i < lenP; i++ {
        charMap[p[i]]++
    }

    var sMap map[byte]int
    sMap = make(map[byte]int)
    for i := 0; i < lenP; i++ {
        sMap[s[i]]++
    }

    for i := 0; i < lenS - lenP + 1; i++ {
        fmt.Printf("%+v
", s[i:i+lenP])
        isAnagrams := true

        var tmpMap map[byte]int
        tmpMap = make(map[byte]int)
        for k, v := range charMap {
            tmpMap[k] = v
        }

        if i > 0 {
            sMap[s[i+lenP-1]]++
            sMap[s[i-1]]--
        }

        for k, v := range sMap {
            if 0 == v {
                continue
            }
            _, ok := tmpMap[k]
            if !ok {
                isAnagrams = false
                break
            }
            tmpMap[k] -= v
        }
        if isAnagrams {
            for _, v := range tmpMap {
                if v > 0 {
                    isAnagrams = false
                    break
                }
            }
        }

        if isAnagrams {
            ret = append(ret, i)
        }
    }

    return ret
}

테스트
findAnagrams_test.go

package _438_Find_All_Anagrams_in_a_String

import "testing"

func equalSlice(s, p []int) bool {
    len1 := len(s)
    len2 := len(p)
    if len1 != len2 {
        return false
    }

    for i := 0; i < len1; i++ {
        if s[i] != p[i] {
            return false
        }
    }

    return true
}

func TestFindAnagrams(t *testing.T) {
    var tests = []struct{
        s string
        p string
        ret []int
    } {
        {"cbaebabacd", "abc", []int{0,6}},
        {"baa", "aa", []int{1}},
    }

    for _, v := range tests {
        ret := FindAnagrams(v.s, v.p)
        if equalSlice(ret, v.ret) {
            t.Logf("pass")
        } else {
            t.Errorf("fail, want %+v, get %+v", v.ret, ret)
        }
    }
}