Find All Anagrams in a String 找變位子串：

本題難度為easy? 當看到題目的第一眼 有些懷疑? 怎么能等級那么簡單? 通過網上找到思路后發現 確實不難? 現整理總結思路

?

原字符串s，在s中尋找字符串p的變位字符串的位置，并依次輸出，且字符串元素均為小寫字母。

思路：首先題目中給定 只有小寫字母 所以可以用一個數組長度26來包含完所有的元素情況 并記錄其對應出現次數 當然首先應該記錄的應該是p的元素的對應次數pvec

然后再s中，從第一個元素開始往后找 在長度一樣時 每次與pvec來比較 與p的元素和所對應的次數是否完全一樣 在這個過程中 與順序無關? 且當s中元素往后移動一位?

前面起始位置都應該后移一位

?

過程：

1、記錄p中元素及其出現次數 ：pvec

2、在s中 從位置0開始依次后移 依次往后記錄當前s中元素出現的次數svec

3、在當前s記錄過程中 長度達到p的長度時? 就要從開始端移除最開始元素了

4、比較svec中元素記錄和pvec中是否相等 相等則表示在這一長度中 找到了p的一個變位子串位置 即為s中當前長度的開始位置 并記錄下來

5、轉第二步 直至s中元素記錄完畢

　

代碼：

vector<int> findAnagrams(string s, string p) {
?? ?vector<int> res;
?? ?if (s.length() < p.length() || s.length() == 0 || p.length() == 0)
?? ??? ?return res;
?? ?vector<int> svec(26), pvec(26);
???
?? ?for (int i = 0; i < p.length(); ++i)
?? ??? ?pvec[p[i] - 'a']++;
?? ?for (int i = 0; i < s.length(); ++i)
?? ?{
?? ??? ?svec[s[i] - 'a']++;
?? ??? ?if (i >= p.length())
?? ??? ??? ?svec[s[i - p.length()] - 'a']--;
?? ??? ?if (svec == pvec)
?? ??? ??? ?res.push_back(i - p.length()+1);
?? ?}
?? ?return res;
}

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

　　　　　

轉載于:https://www.cnblogs.com/weiyi-mgh/p/6291159.html

總結

以上是生活随笔為你收集整理的leetcode 438：Find All Anagrams in a String 找变位子串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。