歡迎來到博主的專欄：算法解析
博主ID：代碼小豪

leetcode438——找到字符串中所有字母異位詞

題目解析

異位詞是指，有相同的英文字母組成的單詞，不要求單詞中的字母順序一致。

以示例1為例：
p中的詞組是"abc"。而在s當中有"cba","bac"這兩個子串，滿足異位詞的條件，因此返回這兩個子串的起始下標位置。

如果s=“cbaebabacd”，p = “abba”。則s中存在子串"baba"滿足異位詞的條件。

返回子串"baba"在s當中的起始下標位置4。

算法原理

首先，我們思考一下，如何證明子串和字符串t的是屬于字母異位詞呢？我們要找到它們的特點，即字母要對應，字母的個數要相同，比如t當中有3個a，1個b，2個c，那么子串也要滿足有3個a，1個b，2個c，不能存在更多的字母，比如d，也不能出現不同的個數，比如5個a。

那么我們可以用哈希表來完成字母與個數的映射。我們可以創建哈希表1，用來映射t中的字母。

因為小寫字母一共有26位，我們可以用int [26]的數組來作為哈希表，而不是STL中的unordered_map。因為STL容器雖然功能強大，但是效率會比數組低一些。

接下來遍歷出整個s中所有大小為4的子串，并且子串中出現的字母映射到另一張哈希表2中。

接下來將hash2出現的結果與hash1挨個作對比，若hash1與hash2一致，則說明該子串是字母異位詞。此時將該下標位置記錄下來。

因此我們需要找到一個遍歷字符串的算法。我們觀察一下上面遍歷的結果。

由于子串的長度是固定的，可以發現，如果我們從左往右遍歷出所有的子串，只需要刪除前一個元素，插入后一個元素即可（橙色為刪除的元素，藍色為插入的元素）。因此我們可以采用滑動窗口的遍歷方式（見上一篇文章，滑動窗口是一種由暴力枚舉優化而來的遍歷算法，可以將遍歷的復雜度從O(N^2)變成O(N)）。

因此我們可以定義出一個left指針，和right指針，使其都指向字符串的起始位置。

由于我們還使用了哈希表來輔助完成對比任務，因此我們要讓right當前指向的元素，插入哈希表中。這步操作稱為進窗口。

當子串的長度等于t的長度時，我們要判斷一下hash1與hash2是否相等，相等就說明子串與t構成異位詞。記錄下left的當前下標（子串的起始位置）。

由于子串需要和字符串t的大小一致（異位詞的定義）。因此我們要保持right-left+1的大小不超過t的字符串長度，在本例中，字符串t為"abab",即長度為4.因此當right-left+1大于4時，我們要讓left指向的元素，在哈希表中被刪除，該操作稱為出窗口，完成出窗口操作后，令left++，如下:

無論是進窗口，還是出窗口，都有可能導致子串的長度與t的長度相等，因此無論是進窗口操作完成后，還是出窗口操作完成后，都要判斷一下hash1和hash2。

最后就是判斷hash1和hash2的方法了，我們可以通過同時遍歷hash1和hash2的方式來完成，但是這么做效率其實并不高，博主這里講解一個優化的算法，優化的方面就是簡化哈希表的判斷。

我們可以使用count來記錄當前子串中的有效字符個數。有效字符指的是當前子串符合構成t的異位詞的字符。比如t為"aacb",子串為"cccb",此時有效字符個數僅為2（因為只有"cb"是符合構成異位詞條件的字符），因此不構成異位詞。當count與t的個數相等時，此時才符合異位詞的條件。

那么如何計算count的值呢？若是hash2中記錄的該字符的計數小于等于hash1中該字符的計數。則說明該字符是一個有效字符。若是進窗口的字符是有效字符，則count++，若是出窗口的字符符合有效字符，則count–。

因此整體的運行邏輯如下:
1.進窗口并判斷需要更新有效字符
2.判斷是否要出窗口，若出窗口則要更新有效字符
3.判斷是否構成異位詞
4.right++。

題解代碼

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int n=p.size();int hash1[26];for(auto e:p){hash1[e-'a']++;}int hash2[26]={0};for(int left=0,right=0,count=0;right<s.size();right++){//進窗口char in=s[right];hash2[in-'a']++;if(hash2[in-'a']<=hash1[in-'a']) count++;//判斷有效字符//出窗口if(right-left+1>n){char out=s[left++];if(hash2[out-'a']<=hash1[out-'a']) count--;//判斷有效字符hash2[out-'a']--;}if(count==n) ret.push_back(left);//判斷是否為異位詞}return ret;}
};

leetcode30——串聯所有單詞的子串

題目解析

這道題的難度確實符合困難，即使是博主在思路非常明確的情況下做這道題依然被許多細節給困擾一段時間。

算法原理

這道題我們可以看做是找到字符串中所有字母異位詞的plus版，為什么這么說呢？我們以示例1為例：

如果我們讓words[0]視為’A’,words[1]視為’b’。未出現在words中的其他字符串等于其他字母，那么s和words會變成下面這樣:

有沒有發現，這道題的解決思路和異位詞的解決思路一模一樣？沒錯，確實如此，我們一樣時創建兩個哈希表，只不過哈希表中不再是字符與計數的映射關系，而是字符串和計數的映射關系，count從有效字符的個數變成了有效字符串的個數，遍歷的方式依然是滑動窗口，這么想這道題的難度是不是從困難變成和異位詞一樣的一般了？

不過我們要注意幾個細節

細節1:字符串s有多種遍歷方式

解決方法:分多次從不同的起始位置遍歷

細節2:
right和left每次移動都要跳向后多個元素，因為這次滑動窗口要遍歷的不是單個字符，而是定長的字符串

而且由于此題涉及較多的字符串操作，因此要求我們對STL庫有一定的熟練度。

題解代碼

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;int len=words[0].size();for(auto& e:words){hash1[e]++;}for(int i=0;i<len;i++){//多次遍歷unordered_map<string,int> hash2;int all=0;//hash2中記錄的字符串總個數int cnt=0;//有效字符串總數for(int left=i,right=left;right+len<=s.size();right+=len){//進窗口string sub=s.substr(right,len);hash2[sub]++;all++;if(hash2[sub]<=hash1[sub]) cnt++;//出窗口if(all>words.size()){string out;out=s.substr(left,len);if(hash2[out]<=hash1[out]) cnt--;hash2[out]--;left+=len;all--;}if(cnt==words.size()) ret.push_back(left);}}return ret;}
};