LeetCode 30. 串聯所有單詞的子串算法對比分析

---

1. 題目鏈接

LeetCode 30. 串聯所有單詞的子串

---

2. 題目描述

給定一個字符串 s 和一個字符串數組 words，words 中所有單詞長度相同。要求找到 s 中所有起始索引，使得從該位置開始的連續子串包含 words 中所有單詞的某種排列（不限制順序）。
示例：
輸入：s = "barfoothefoobarman", words = ["foo","bar"]
輸出：[0,9]（子串 "barfoo" 和 "foobar" 符合條件）。

---

3. 算法思路

滑動窗口法：

1. 問題轉化：將 words 的排列匹配問題轉化為固定窗口長度的滑動窗口問題。
2. 哈希表統計：用 hash1 記錄 words 中單詞的出現次數，hash2 記錄當前窗口內單詞的出現次數。
3. 多起點遍歷：由于單詞長度固定為 nwSub，需遍歷 nwSub 種可能的起始偏移（0 ≤ i < nwSub）。
4. 窗口動態調整：
   • 右指針擴展：每次截取一個單詞加入窗口，更新哈希表。
   • 左指針收縮：當窗口內單詞數量超過 nw 時，移動左指針。
5. 結果判斷：當窗口內單詞數量等于 nw 且所有單詞頻率匹配時，記錄起始索引。

暴力枚舉法：

1. 遍歷所有子串：枚舉所有長度為 nw * nwSub 的子串。
2. 分割統計：將子串分割為 nw 個單詞，統計頻率是否與 words 一致。

---

4. 示例分析

輸入：s = "barfoothefoobarman", words = ["foo","bar"]

1. 暴力枚舉法：

   • 枚舉所有長度為 6 的子串，例如 "barfoo", "arfoot", "rfooth" 等。
   • 對每個子串分割為 ["bar","foo"] 或 ["arf","oot"]，檢查是否與 words 匹配。

2. 滑動窗口法：

   • 當 i=0 時，窗口從 left=0 開始，截取 "bar" 和 "foo"，count=2，記錄索引 0。
   • 當 i=9 時，窗口從 left=9 開始，截取 "foo" 和 "bar"，count=2，記錄索引 9。

---

5. 邊界條件與注意事項

1. 單詞長度相同：words 中所有單詞長度必須一致。
2. 空輸入處理：若 words 為空或 s 長度不足，直接返回空。
3. 哈希表更新：需在收縮窗口時及時減少 hash2 的計數，避免無效單詞干擾。

---

6. 代碼實現

class Solution 
{
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;int ns = s.size(), nw = words.size(), nwSub = words[0].size();if (ns < nwSub * nw) return ret;unordered_map<string, int> hash1;for (auto& word : words) hash1[word]++;for (int i = 0; i < nwSub; i++) { // 遍歷所有可能的起始偏移unordered_map<string, int> hash2;int left = i, count = 0; // left為窗口左邊界for (int right = i; right + nwSub <= ns; right += nwSub) {// 截取當前單詞string in = s.substr(right, nwSub);hash2[in]++;// 更新有效計數：僅在當前單詞屬于hash1且未超過次數時增加countif (hash1.count(in) && hash2[in] <= hash1[in]) count++;// 當窗口內的單詞數量超過nw時，收縮左邊界while ((right - left) / nwSub + 1 > nw) {string out = s.substr(left, nwSub);if (hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left += nwSub; // 左指針移動一個單詞長度}// 若有效計數等于nw，記錄起始索引if (count == nw) ret.push_back(left);}}return ret;}
};

---

7.暴力枚舉法與滑動窗口法對比圖表

對比維度	暴力枚舉法	滑動窗口法
核心思想	枚舉所有長度為 nw * nwSub 的子串，分割后比較單詞頻率。	維護固定窗口長度，動態調整窗口內的單詞頻率。
時間復雜度	O(ns * nw * nwSub)（每個子串需分割并統計頻率）。	O(ns * nwSub)（每個單詞被處理一次）。
空間復雜度	O(nw)（存儲 words 的哈希表）。	O(nw)（存儲兩個哈希表）。
實現方式	雙重循環遍歷子串，內層循環分割并統計。	單層循環擴展右指針，動態調整左指針。
適用場景	小規模數據（ns ≤ 1e3, nw ≤ 10）。	大規模數據（ns ≤ 1e5）。
優點	邏輯簡單，直接窮舉所有可能性。	時間復雜度低，適用于大規模數據。
缺點	數據規模大時性能極差（例如 ns=1e4 時需 1e8 次操作）。	需處理哈希表的動態更新和邊界條件。