438. Find All Anagrams in a String

題目

給定一個字串 s，找出所有的substring屬於另一個字串 p 的 anagram，回傳所有符合條件的index

anagram即同分異構物，substring不限順序，與 p 含有一樣的字母與數量

限制

1 <= s.length, p.length <= 3 * 104
s and p consist of lowercase English letters.

思考一些test case

不會有空字串
s = “abc“, p = “abc“ ⇒ [0]
s = “abc“, p = “abcd” ⇒ p 長度大於 s，無解
s = “abababababa”, p = “ab” ⇒ 每個長度為2的substring都是解
s = “abba”, p = “aab” ⇒ 重複元素只能用一次，abb不算解答

解題思路

檢查是否為anagram，就在檢查每個 p.size()的substring是否為anagram
- 需要走過 s.size() - p.size() 次搜尋
- 每次檢查需要 p.size()
當 s = “abcdcba“p = “abc”
1. [abc]dcba
2. a[bcd]cba
3. ab[cdc]ba
4. abc[dcb]a
5. abcd[cba]
由上列執行順序可觀察到檢查的範圍內每次會移除第一個，並加入下一個字母，只要記錄第window內每個字母的數量，每次移動window時只需要修改記數就能知道window內與p匹配的字母數量
只要比對目前 window 內匹配數是否與p相等就能知道是否為 anagram
為了處理重複字母的問題，用一個hash map來記錄p的每一個字母數量，與window內的數量相減，只要小於0表示該字母已經全部匹配到，匹配數就不應該增加，反之字母被移除出window時若該字母大於或等於0則表示匹配的字母被移除，匹配數須減一

Dry run

s = “aaabaaa”, p = “aab”

初始hash map

{ a ⇒ 2, b ⇒ 1 }

[aaa]baaa
1. { a ⇒ -1, b ⇒ 1 }
2. 匹配數 2 (p內只有兩個a)
a[aab]aaa，(a + 1, b - 1)
1. { a ⇒ 0, b ⇒ 0 }
2. 匹配數為 3，加入答案列表
  1. a 為負值，代表window內的a本來就太多，移除不影響匹配
  2. b為正值且不為0，代表匹配長度 + 1
aa[aba]aa，(a + 1, a - 1)
1. { a ⇒ 0, b ⇒ 0 }
2. 匹配數為3，是答案之一
  1. a 移除時為0，代表數量剛好，移除會減少匹配長度
  2. a 加入時為1，代表缺少這個字母，加入會讓匹配長度加一
aaa[baa]a，同上
1. { a ⇒ 0, b ⇒ 0 }
aaab[aaa]，(b + 1, a - 1)
1. { a ⇒ -1, b ⇒ 1 }
2. 匹配數為2，非答案
  1. 移除b，記數為0，減少匹配值
  2. 加入a，記數為0，代表這個a是多餘的，不影響匹配值

Coding思路

判斷 s 及 p 的長度有沒有執行必要(p.size() > s.size())
建立 p 的字母記數map
初始化第一個window，同時計算匹配值 match
若 match 與 p 等長，先加入答案
執行sliding window直到 s[(s.size() - p.size()) .. (s.size() - 1)]
1. 執行完加入/移除字母操作後，由 match判斷需不需要加到答案

Solution

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (p.size() > s.size()) {
            return {};
        }

        vector<int> ans;
        unordered_map<char, int> m;
        for (const char ch : p) {
            m[ch] += 1;
        }

        int match = 0;
        for (int i = 0; i < p.size(); i += 1) {
            if (m.find(s[i]) != m.end()) {
                if (m[s[i]] > 0) {
                    match += 1;
                }
                m[s[i]] -= 1;
            }
        }

        if (match == p.size()) {
            ans.push_back(0);
        }

        for (int i = 0; i + p.size() < s.size(); i += 1 ) {
            if (m.find(s[i]) != m.end()) {
                if (m[s[i]] >= 0) {
                    match -= 1;
                }
                m[s[i]] += 1;
            }

            if (m.find(s[i + p.size()]) != m.end()) {
                if (m[s[i + p.size()]] > 0) {
                    match += 1;
                }
                m[s[i + p.size()]] -= 1;
            }

            if (match == p.size()) {
                ans.push_back(i + 1);
            }
        }
        return ans;
    }
};

題目​

限制​

思考一些test case​

解題思路​

Dry run​

Coding思路​

Solution​

題目

限制

思考一些test case

解題思路

Dry run

Coding思路

Solution