未分類

Find All Anagrams in a String

Go, HashTable, LeetCode

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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
10
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".
提示 解題應用
HashTable HashMap

Default:

1
2
3
func findAnagrams(s string, p string) []int {
}

解答思路:

這題卡了非常久在於一開始的思路有點問題，在於重設次數上的判斷，通常要這類找一字串是否包含另一字串，且被包含的字串不需要在意其順序的話，會用hashmap來儲存，其中key為被包含的字母，而value則是出現的次數，該字串包含其字母則次數-1，一直到所有字母出現的次數皆為0，甚至被包含字串的每個字母不需要連結著，只要字母有完全出現的話，只要次數一歸0直接從hashmap拿掉最後在判斷hashmap是否為空即可，但此題雖然不需在意順序，但字串是完整連結，這意味著如果在核對是否包含時，如果到一半發現主字串前半部並不完全包含著次字串，但有可能是主次串的後半部才會出現，此時是不是該重設原本字母出現的次數並重新判斷，偏偏如果差一個字母，只要往下移一格再重新檢查就符合條件，如果照剛剛完全重設大部分已經判斷過的字母，是非常浪費時間的，所以不是把所有次數重設，而是邊移動邊判斷，如果出現不符合條件，把最前面最早判斷的字母次數(hashmap之中，不在其中就不用)給加一個回來，之後再向後推一格再把最新的字母做比對並判斷是否hashmap此時所有的字母次數都已經歸0，藉由這樣的方式慢慢向後推，每次一發現所有字母次數歸0就紀錄index值，如此一來就算所有符合條件的次字串彼此互相重疊也可以很容易全部找出來。

程式碼解說:

一開始當然是先初始化一hashmap，其中key值為rune型別，value則是字母出現的次數，接著利用迴圈遍歷將被包含字串的每個字母放入hashmap之中，同時計算出現的次數

1
2
3
4
5
6
7
var result []int
var flag int
var front int
hashMap := make(map[rune]int)
for _, v := range p {
	hashMap[v]++
}

再來開始遍歷我們的主字串，先看該字母是否存在於hashMap之中，如果存在就將該字母的次數-1，當字母的次數為0時，就記錄下已經有多少個字母歸0，如果所有hashmap字母皆歸0，表示次字串存在於主字串之中，並且將次字串的第一個index值front放入結果之中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for i, v := range s {
	...
	amount, ok := hashMap[v]
	if ok {
		hashMap[v]--
		amount--
		if amount == 0 {
			flag++
		}
		if flag == len(hashMap) {
			result = append(result, front)
		}
	}
}
return result

當遍歷的index減去開頭的index等於次字串的長度時(比次字串長度多1)，這時就需要將次字串向後位移一格，因為向後移時原本包含的第一個字母會移出計算的次數，所以如果是在hashmap之中的話要將該字母的字數加回1，如果原本的數量已經歸0，要記得將原本記錄下已經有多少個字母歸0再加回1，最後才接回上一段解說的程式碼檢查後移一格加入新包含的字母後，是否又符合包含次字串的條件

1
2
3
4
5
6
7
8
9
10
11
12
for i, v := range s {
	if i-front == len(p) {
		amount, ok := hashMap[rune(s[front])]
		if ok {
			hashMap[rune(s[front])]++
			if amount == 0 {
				flag--
			}
		}
		front++
	...
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func findAnagrams(s string, p string) []int {
	var result []int
	var flag int
	var front int
	hashMap := make(map[rune]int)
	for _, v := range p {
		hashMap[v]++
	}
	for i, v := range s {
		if i-front == len(p) {
			amount, ok := hashMap[rune(s[front])]
			if ok {
				hashMap[rune(s[front])]++
				if amount == 0 {
					flag--
				}
			}
			front++
		}
		amount, ok := hashMap[v]
		if ok {
			hashMap[v]--
			amount--
			if amount == 0 {
				flag++
			}
			if flag == len(hashMap) {
				result = append(result, front)
			}
		}
	}
	return result
}

總結:

要判斷一字串(主字串)是否包含另一字串(次字串)，且被包含的字串不需順序排列但字母間需連結，首先先將被包含字串的字母用hashmap作儲存，其中key為字母而value則是出現的次數，在主字串上邊移動邊判斷，符合條件就將該字母次數-1，如果主字串上的次字串出現不符合條件的情況，把最前面最早判斷的字母次數(hashmap之中，不在其中就不用)給加一個回來，之後再向後推一格再把最新的字母做比對並判斷是否hashmap此時所有的字母次數都已經歸0，藉由這樣的方式慢慢向後推，每次一發現所有字母次數歸0就紀錄index值，如此一來就算所有符合條件的次字串彼此互相重疊也可以很容易全部找出來。

分享到