問題描述
給定一個字符串?s?和一個字符串數組?words。?words?中所有字符串?長度相同。
?s?中的?串聯子串?是指一個包含??words?中所有字符串以任意順序排列連接起來的子串。
- 例如，如果?
words = ["ab","cd","ef"]， 那么?"abcdef"，?"abefcd"，"cdabef"，?"cdefab"，"efabcd"， 和?"efcdab"?都是串聯子串。?"acdbef"?不是串聯子串，因為他不是任何?words?排列的連接。
返回所有串聯子串在?s?中的開始索引。你可以以?任意順序?返回答案。
解題思路
1. 初步理解
首先需要明確，只有當 s 中的某個子串正好由 words 中所有單詞組成，并且每個單詞出現一次，才符合條件。這提示我們可以使用組合和檢查的策略來找到這些子串。
2. 設計策略
基于以上理解，可以采用以下策略：
- 長度計算: 計算
words中所有字符串連接后的總長度，這將是我們在s中搜索的子串的長度。 - 字典統計: 使用一個哈希表（字典）來統計
words數組中每個單詞的出現頻率。 - 滑動窗口: 在字符串
s上滑動一個固定大小的窗口，并在窗口內部維護一個字典來記錄當前窗口中各單詞的出現頻率。 - 窗口調整: 根據窗口內單詞的實際出現情況，調整窗口的開始位置，確保窗口內的單詞頻率與
words中的單詞頻率相匹配。
3. 實現細節
- 初始化: 計算每個單詞的長度
wordLength，所有單詞的數量wordCount，以及應搜索的窗口大小windowSize。 - 遍歷: 遍歷字符串
s的每個可能的起始位置，步長為wordLength。 - 內部循環: 對每個起始位置，向右滑動窗口，每次移動一個單詞的長度，直到窗口尾部超出字符串
s的邊界。 - 檢查與調整: 每次窗口滑動后，更新當前單詞在窗口中的計數，并與
words字典進行比較，如果當前單詞計數超過了應有的頻率，則調整窗口的左邊界，直至窗口內的單詞頻率再次符合要求。 - 記錄結果: 如果窗口大小達到了
windowSize，且窗口內的單詞與words中的單詞完全匹配，則記錄當前窗口的起始位置。
代碼實現
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> indices;if (s.empty() || words.empty())return indices;int wordLength = words[0].size();int wordCount = words.size();int windowSize = wordLength * wordCount;if (s.size() < windowSize)return indices;// 記錄words中每個單詞出現的次數unordered_map<string, int> wordMap;for (const string& word : words) {++wordMap[word];}// 檢查每個可能的開始位置for (int i = 0; i < wordLength; ++i) {int left = i;int right = i;unordered_map<string, int> currentMap;while (right + wordLength <= s.size()) {string word = s.substr(right, wordLength);right += wordLength;if (wordMap.find(word) != wordMap.end()) {++currentMap[word];// 處理單詞出現次數過多的情況while (currentMap[word] > wordMap[word]) {string leftWord = s.substr(left, wordLength);--currentMap[leftWord];left += wordLength;}// 檢查是否形成了一個有效的窗口if (right - left == windowSize) {indices.push_back(left);string leftWord = s.substr(left, wordLength);--currentMap[leftWord];left += wordLength;}} else {currentMap.clear();left = right;}}}return indices;}
};
