Hard

题目描述

给定一个字符串 s 和一个字符串数组 words。words 中所有字符串长度相同。

串联字符串是一个字符串，它恰好包含 words 中所有字符串的任意排列的串联。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"、"abefcd"、"cdabef"、"cdefab"、"efabcd" 和 "efcdab" 都是串联字符串。"acdbef" 不是串联字符串，因为它不是 words 的任何排列的串联。

返回 s 中所有串联子串的起始索引。你可以以任意顺序返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 开始的子串是 "barfoo"。它是 ["bar","foo"] 的串联，这是 words 的一个排列。
从索引 9 开始的子串是 "foobar"。它是 ["foo","bar"] 的串联，这是 words 的一个排列。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：没有串联子串。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：
从索引 6 开始的子串是 "foobarthe"。它是 ["foo","bar","the"] 的串联。
从索引 9 开始的子串是 "barthefoo"。它是 ["bar","the","foo"] 的串联。
从索引 12 开始的子串是 "thefoobar"。它是 ["the","foo","bar"] 的串联。

提示：

  • 1 <= s.length <= 10^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s 和 words[i] 由小写英文字母组成

解题思路

这道题可以用滑动窗口+哈希表的方法来解决。

核心思路：

  1. 首先统计 words 数组中每个单词的出现次数，用哈希表存储
  2. 由于每个单词长度相同，设为 wordLen，总长度为 totalLen = wordLen * words.length
  3. 在字符串 s 中，以每个位置为起点，尝试匹配长度为 totalLen 的子串
  4. 将子串按 wordLen 分割成单词，统计每个单词出现次数，与目标哈希表比较

优化方法： 可以用滑动窗口优化。对于每个可能的起始位置（0 到 wordLen-1），使用滑动窗口在该"轨道"上移动，这样可以避免重复计算，将时间复杂度从 O(nmk) 优化到 O(n*k)，其中 n 是字符串长度，m 是单词个数，k 是单词长度。

推荐解法： 滑动窗口优化版本，既高效又易于理解。

具体实现时，对于每个起始偏移量（0到wordLen-1），维护一个滑动窗口，当窗口内单词匹配时记录结果，当不匹配时调整窗口位置。

代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (s.empty() || words.empty()) return result;
        
        int wordLen = words[0].length();
        int wordCount = words.size();
        int totalLen = wordLen * wordCount;
        
        if (s.length() < totalLen) return result;
        
        // 统计words中每个单词的出现次数
        unordered_map<string, int> wordMap;
        for (const string& word : words) {
            wordMap[word]++;
        }
        
        // 对每个可能的起始偏移量使用滑动窗口
        for (int offset = 0; offset < wordLen; offset++) {
            unordered_map<string, int> windowMap;
            int left = offset, count = 0;
            
            for (int right = offset; right <= (int)s.length() - wordLen; right += wordLen) {
                string word = s.substr(right, wordLen);
                
                if (wordMap.find(word) != wordMap.end()) {
                    windowMap[word]++;
                    count++;
                    
                    // 如果某个单词出现次数超过要求，需要移动左边界
                    while (windowMap[word] > wordMap[word]) {
                        string leftWord = s.substr(left, wordLen);
                        windowMap[leftWord]--;
                        count--;
                        left += wordLen;
                    }
                    
                    // 如果窗口大小正确且所有单词匹配，记录结果
                    if (count == wordCount) {
                        result.push_back(left);
                        string leftWord = s.substr(left, wordLen);
                        windowMap[leftWord]--;
                        count--;
                        left += wordLen;
                    }
                } else {
                    // 遇到不在words中的单词，重置窗口
                    windowMap.clear();
                    count = 0;
                    left = right + wordLen;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        
        word_len = len(words[0])
        word_count = len(words)
        total_len = word_len * word_count
        
        if len(s) < total_len:
            return []
        
        # 统计words中每个单词的出现次数
        word_map = {}
        for word in words:
            word_map[word] = word_map.get(word, 0) + 1
        
        result = []
        
        # 对每个可能的起始偏移量使用滑动窗口
        for offset in range(word_len):
            window_map = {}
            left = offset
            count = 0
            
            for right in range(offset, len(s) - word_len + 1, word_len):
                word = s[right:right + word_len]
                
                if word in word_map:
                    window_map[word] = window_map.get(word, 0) + 1
                    count += 1
                    
                    # 如果某个单词出现次数超过要求，需要移动左边界
                    while window_map[word] > word_map[word]:
                        left_word = s[left:left + word_len]
                        window_map[left_word] -= 1
                        count -= 1
                        left += word_len
                    
                    # 如果窗口大小正确且所有单词匹配，记录结果
                    if count == word_count:
                        result.append(left)
                        left_word = s[left:left + word_len]
                        window_map[left_word] -= 1
                        count -= 1
                        left += word_len
                else:
                    # 遇到不在words中的单词，重置窗口
                    window_map.clear()
                    count = 0
                    left = right + word_len
        
        return result

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        var result = new List<int>();
        if (string.IsNullOrEmpty(s) || words.Length == 0) return result;
        
        int wordLen = words[0].Length;
        int wordCount = words.Length;
        int totalLen = wordLen * wordCount;
        
        if (s.Length < totalLen) return result;
        
        // 统计words中每个单词的出现次数
        var wordMap = new Dictionary<string, int>();
        foreach (string word in words) {
            if (wordMap.ContainsKey(word)) {
                wordMap[word]++;
            } else {
                wordMap[word] = 1;
            }
        }
        
        // 对每个可能的起始偏移量使用滑动窗口
        for (int offset = 0; offset < wordLen; offset++) {
            var windowMap = new Dictionary<string, int>();
            int left = offset, count = 0;
            
            for (int right = offset; right <= s.Length - wordLen; right += wordLen) {
                string word = s.Substring(right, wordLen);
                
                if (wordMap.ContainsKey(word)) {
                    if (windowMap.ContainsKey(word)) {
                        windowMap[word]++;
                    } else {
                        windowMap[word] = 1;
                    }
                    count++;
                    
                    // 如果某个单词出现次数超过要求，需要移动左边界
                    while (windowMap[word] > wordMap[word]) {
                        string leftWord = s.Substring(left, wordLen);
                        windowMap[leftWord]--;
                        count--;
                        left += wordLen;
                    }
                    
                    // 如果窗口大小正确且所有单词匹配，记录结果
                    if (count == wordCount) {
                        result.Add(left);
                        string leftWord = s.Substring(left, wordLen);
                        windowMap[leftWord]--;
                        count--;
                        left += wordLen;
                    }
                } else {
                    // 遇到不在words中的单词，重置窗口
                    windowMap.Clear();
                    count = 0;
                    left = right + wordLen;
                }
            }
        }
        
        return result;
    }
}

var findSubstring = function(s, words) {
    if (!s || !words || words.length === 0) return [];
    
    const wordLen = words[0].length;
    const totalLen = wordLen * words.length;
    const result = [];
    
    if (s.length < totalLen) return [];
    
    const wordCount = {};
    for (const word of words) {
        wordCount[word] = (wordCount[word] || 0) + 1;
    }
    
    for (let i = 0; i < wordLen; i++) {
        let left = i;
        let count = 0;
        const windowCount = {};
        
        for (let right = i; right <= s.length - wordLen; right += wordLen) {
            const word = s.substring(right, right + wordLen);
            
            if (wordCount[word]) {
                windowCount[word] = (windowCount[word] || 0) + 1;
                count++;
                
                while (windowCount[word] > wordCount[word]) {
                    const leftWord = s.substring(left, left + wordLen);
                    windowCount[leftWord]--;
                    if (windowCount[leftWord] === 0) {
                        delete windowCount[leftWord];
                    }
                    left += wordLen;
                    count--;
                }
                
                if (count === words.length) {
                    result.push(left);
                    const leftWord = s.substring(left, left + wordLen);
                    windowCount[leftWord]--;
                    if (windowCount[leftWord] === 0) {
                        delete windowCount[leftWord];
                    }
                    left += wordLen;
                    count--;
                }
            } else {
                windowCount = {};
                count = 0;
                left = right + wordLen;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × k)n是字符串s的长度，k是单词长度。滑动窗口优化后每个字符最多被访问常数次
空间复杂度O(m × k)m是words数组的长度，k是单词长度，主要用于存储哈希表

相关题目