目錄

1.題目

2.分析

暴力解法

方法1:排序(超時)

方法2:哈希表(險過)

★判斷兩個哈希表是否相同算法(通用方法,必須掌握)

能相等的前提:兩個哈希表的大小相等

哈希表有迭代器,可以使用范圍for從頭到尾遍歷

提交結果

優化方法:定長滑動窗口

提交結果

使用哈希數組更快

提交結果

★★★更優化的方法:不定長滑動窗口(比定長的要快!)

提交結果

---

1.題目

https://leetcode.cn/problems/find-all-anagrams-in-a-string/

給定兩個字符串?s?和 p，找到?s?中所有?p?的?

?的子串，返回這些子串的起始索引。不考慮答案輸出的順序。

示例?1:

輸入: s = "cbaebabacd", p = "abc"
輸出: [0,6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的異位詞。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的異位詞。

?示例 2:

輸入: s = "abab", p = "ab"
輸出: [0,1,2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的異位詞。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的異位詞。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s?和?p?僅包含小寫字母

2.分析

暴力解法

大致思路:使用i遍歷字符串s,從i位置截取和p相同長度的子串(前提p.size()<=s.size(),這個要在一開始就要判斷),比較這個子串和p是否是異位詞

方法1:排序(超時)

可以先對兩個串排序,再調用operator==判斷是否相等

class Solution {
public:vector<int> findAnagrams(string s, string p){if (p.size()>s.size())return {};vector<int> ret;sort(p.begin(),p.end());for (int i = 0; i <= s.size() - p.size(); i++){string tmp=s.substr(i,p.size());sort(tmp.begin(),tmp.end());if (p==tmp)ret.push_back(i);}return ret;}
};

調用sort函數的時間復雜度是,過高容易超時:

方法2:哈希表(險過)

統計s的子串和p串的詞頻,記錄到哈希表中,再判斷兩個哈希表是否相同,這個時間復雜度比方法1低一點

★判斷兩個哈希表是否相同算法(通用方法,必須掌握)

雖然可以用哈希數組hash['z'+1]投機取巧(這個解法在本文的最后),但是其他題可能用不了哈希數組,因此掌握通用的方法是很有必要的

算法:

能相等的前提:兩個哈希表的大小相等

if (mp1.size() != mp2.size()) return false;

哈希表有迭代器,可以使用范圍for從頭到尾遍歷

STL的map底層實現是紅黑樹,對于for (const auto& pair : mp1),pair拿到的是mp1的紅黑樹中一個節點,到mp2中查有沒有相同的節點即可,使用find函數

find函數的查找邏輯:

cplusplus網上是這樣說的:https://legacy.cplusplus.com/reference/map/map/find/

find取得(get)指向元素的迭代器(iterator to element)

在容器中查找一個鍵值與k等價的元素,如果找到,則返回指向該元素的迭代器;否則返回指向map::end的迭代器

比較時會出現兩種情況

1.找到一個鍵值與k等價的元素,此時還不能斷定兩個節點一定相等,需要比較第二個關鍵字(pair.second)是否相等,如果不等(it->second != pair.second),返回false

2.沒找到一個鍵值與k等價的元素(it == mp2.end()),返回false

class Solution {
public:bool check(map<int,int>& mp1,map<int,int>& mp2){if (mp1.size() != mp2.size()) return false;for (const auto& pair : mp1) {auto it = mp2.find(pair.first);if (it == mp2.end() || it->second != pair.second) return false;}return true;}vector<int> findAnagrams(string s, string p){if (p.size()>s.size())return {};vector<int> ret;map<int,int> mp1;for (int i=0;i<p.size();i++)mp1[p[i]]++;for (int i = 0; i <= s.size() - p.size(); i++){map<int,int> mp2;string tmp=s.substr(i,p.size());for (int i=0;i<tmp.size();i++)mp2[tmp[i]]++;if (check(mp1,mp2))ret.push_back(i);}return ret;}
};

提交結果

優化方法:定長滑動窗口

以s = "cbaebabacd", p = "abc"為例分析:

異位詞子串首先要長度和p從串相等,對s從頭到尾遍歷即可,

在移動窗口時,注意左側元素離開哈希表,右側元素加入哈希表,當mp2[s[left]]==0時,必須刪除這個節點,否則影響哈希表的結構

class Solution {
public:bool check(map<int,int>& mp1,map<int,int>& mp2){if (mp1.size() != mp2.size()) return false;for (const auto& pair : mp1) {auto it = mp2.find(pair.first);if (it == mp2.end() || it->second != pair.second) return false;}return true;}vector<int> findAnagrams(string s, string p){if (p.size()>s.size())return {};vector<int> ret;map<int,int> mp1,mp2;for (int i=0;i<p.size();i++){mp1[p[i]]++;mp2[s[i]]++;}for (int left=0,right=p.size()-1; right<s.size();left++,right++){if (check(mp1,mp2)){ret.push_back(left);}mp2[s[left]]--;mp2[s[right+1]]++;if (mp2[s[left]]==0)mp2.erase(s[left]);}return ret;}
};

注:right+1最大為s.size(),此時mp2[s[right+1]]++;訪問到字符串的'\0'沒有越界,不影響結果?

提交結果

使用哈希數組更快

將map<int,int>改成數組,其他地方稍作修改即可

class Solution {
public:bool check(int* mp1,int* mp2){for(int i='a';i<='z';i++)if (mp1[i]!=mp2[i])return false;return true; }vector<int> findAnagrams(string s, string p){if (p.size()>s.size())return {};vector<int> ret;int mp1['z'+1]={0},mp2['z'+1]={0};for (int i=0;i<p.size();i++){mp1[p[i]]++;mp2[s[i]]++;}for (int left=0,right=p.size()-1; right<s.size();left++,right++){if (check(mp1,mp2))ret.push_back(left);mp2[s[left]]--;mp2[s[right+1]]++;}return ret;}
};

提交結果

★★★更優化的方法:不定長滑動窗口(比定長的要快!)

hash_s是字符串s的滑動窗口的哈希數組,hash_p是字符串p的的哈希數組

上面的優化的方法還可以繼續優化,引入有效字符的個數:

先讓hash_s[s[right]]++,之后判斷:

1.當hash_s[s[right]] <= hash_p[s[right]]時計入有效字符的個數count,即count++

2.一旦窗口長度大于len時,及時調整讓left++,當hash_s[s[left]] <= hash_p[s[left]]時減小有效字符的個數count,即count--

★更新結果的條件:窗口長度相等,且有效字符的個數要相等,這樣就不用像上面方法那樣遍歷mp1和mp2數組的每個元素

個數從0變成1,有效字符的個數+1,因此count++

個數從1變成0,有效字符的個數-1,因此count--

符合有效字符的個數==p串的長度,將left尾插到返回數組ret

class Solution {
public:vector<int> findAnagrams(string s, string p) {if (p.size() > s.size())return {};vector<int> ret;int len = p.size();int count = 0;int hash_s['z'+1] = {0}, hash_p['z'+1] = {0};for (int i = 0; i < p.size(); i++)hash_p[p[i]]++;for (int left = 0, right = 0; right < s.size(); right++) {hash_s[s[right]]++;if (hash_s[s[right]] <= hash_p[s[right]])count++;if (right - left + 1 > len) {if (hash_s[s[left]] <= hash_p[s[left]])count--;hash_s[s[left]]--;left++;}if (count == len)ret.push_back(left);}return ret;}
};

提交結果