問題描述

給定兩個字符串s和p，找到s中所有p的?異位詞?的子串，返回這些子串的起始索引。不考慮答案輸出的順序。

異位詞?指由相同字母重排列形成的字符串（包括相同的字符串）。

解題思路1

注意：該解題思路是錯誤的，正確的是解題思路2

這道題目首先想到的肯定是通過多層循環來遍歷：

1. 提取子串：遍歷s字符串，提取長度和p相同的子串
2. 字符匹配：創建p的副本，對于提取的子串中的每個字符，嘗試在p的副本中找到并移除。如果某個字符在p的副本中不存在，說明該子串不是異位詞。
3. 結果記錄：如果所有字符都成功匹配并且p的副本被完全清空，將當前起始位置添加到結果中。

代碼實現

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> results;int p_len = p.length();int s_len = s.length();if (s_len < p_len)return results;// 遍歷s中的每個可能的起始位置for (int start = 0; start <= s_len - p_len; ++start) {string substr = s.substr(start, p_len); // 獲取當前考慮的子串string temp_p = p; // 創建p的一個副本以供修改// 遍歷當前子串中的每個字符bool matched = true;for (char c : substr) {size_t pos = temp_p.find(c); // 在p的副本中查找當前字符if (pos != string::npos) {temp_p.erase(pos, 1); // 如果找到，從p的副本中移除該字符} else {matched = false; // 如果未找到，標記不匹配并跳出循環break;}}if (matched && temp_p.empty()) { // 檢查是否所有p中的字符都被匹配results.push_back(start);}}return results;}
};

當提交答案時提示“超出時間限制”。

回頭來看這里的問題：

這種方法的時間復雜度較高，因為它涉及到在每個可能的子串中對每個字符進行查找和刪除操作，每次刪除操作可能涉及到字符串的重構，其時間復雜度最壞情況下接近O(n * m^2)，其中n是字符串s的長度，m是字符串p的長度。這可能在輸入字符串較長時導致性能問題。

解題思路2

通過對上面思路的反思，我認為這道題嗎不能用多層循環嵌套處理，所以還是從題目本身出發。

我發現最核心的就是如何判斷子串是否為異位詞，上面通過循環遍歷比較來判斷的效率太低，就不能用循環遍歷比較了。

核心思路：因為異位詞不關心字符的順序，只關心字符能不能被匹配上，那就是要判斷字符在子串中出現的次數和出現在p的次數是否相同，如果相同就說明子串屬于異位詞。

解決這一問題的核心思路是利用滑動窗口技術和字符頻率統計：

1. 字符頻率統計：首先，我們需要一個方式來快速判斷兩個字符串是否為異位詞。最直接的方法是使用一個固定大小為26的數組（假設輸入字符串只包含小寫字母）來統計每個字母在字符串中出現的頻率。

2. 滑動窗口：這是一種常用于處理數組和字符串的技術。基本思想是維護一個窗口，這個窗口可以增大也可以縮小，隨著窗口的滑動，我們可以在O(1)的時間內更新窗口內的信息。在這個問題中，我們將窗口的大小固定為字符串p的長度，并在s中從左到右滑動這個窗口。

代碼實現

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;if (s.size() < p.size())return result;// 創建字符頻率表vector<int> p_count(26, 0), s_count(26, 0);for (char c : p) {p_count[c - 'a']++;}int left = 0, right = 0, p_length = p.size();while (right < s.size()) {// 增加右側字符頻率s_count[s[right] - 'a']++;// 當窗口大小等于p的長度時，比較兩個頻率表if (right - left + 1 == p_length) {if (s_count == p_count) {result.push_back(left);}// 移動窗口，減少左側字符頻率s_count[s[left] - 'a']--;left++;}right++;}return result;}
};