30.串联所有单词的子串 python

串联所有单词的子串

题目
- 题目描述
- 示例 1：
- 示例 2：
- 示例 3：
- 提示：
- 题目链接
题解
- 解题思路
- python实现
- 代码解释：
- 提交结果

题目

题目描述

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

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]，那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

提示：

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

题目链接

串联所有单词的子串

题解

解题思路

为了解决这个问题，我们可以使用滑动窗口和哈希表相结合的方法。基本思路是：

计算单词长度和总长度：首先计算每个单词的长度 word_len 和所有单词串联起来的总长度 total_len。
创建一个计数器：使用 Counter 来统计 words 中每个单词出现的次数。
遍历字符串 s：使用滑动窗口的方式遍历字符串 s，检查每个可能的起始位置是否可以形成一个有效的串联子串。

具体步骤如下：

对于每个起始位置，我们尝试构建一个与 words 总长度相等的子串，并检查这个子串中的单词是否符合 words 的计数要求。
如果找到了一个匹配的子串，则记录下它的起始索引。
为了避免重复计算，当窗口大小超过 total_len 时，移除最左边的单词并继续检查。

python实现

下面是 Python 实现代码：

from collections import Counter, defaultdict

def findSubstring(s: str, words: list) -> list:
    if not s or not words:
        return []

    word_len = len(words[0])
    total_len = len(words) * word_len
    word_count = Counter(words)
    result_indices = []

    # Iterate over possible starting offsets
    for offset in range(word_len):
        window_counter = Counter()
        start = offset
        count = 0
        
        for i in range(offset, len(s) - word_len + 1, word_len):
            word = s[i:i + word_len]
            
            if word in word_count:
                window_counter[word] += 1
                count += 1
                
                while window_counter[word] > word_count[word]:
                    left_word = s[start:start + word_len]
                    window_counter[left_word] -= 1
                    start += word_len
                    count -= 1
                
                if count == len(words):
                    result_indices.append(start)
                    # Move the window forward by one word to look for next match
                    left_word = s[start:start + word_len]
                    window_counter[left_word] -= 1
                    start += word_len
                    count -= 1
            else:
                # Reset the window if a word is not in words
                window_counter.clear()
                start = i + word_len
                count = 0
    
    return result_indices

代码解释：

滑动窗口：我们使用了一个宽度为 total_len 的滑动窗口来遍历字符串 s。每次移动一个单词长度（word_len），并更新窗口内的单词计数。
Counter：用来追踪当前窗口内各个单词的数量，确保它们不超过 words 中的数量。
Offset 循环：由于单词长度固定，我们只需要对每个可能的起始偏移量（从 0 到 word_len - 1）执行一次完整的扫描即可覆盖所有情况。
边界条件处理：当遇到不在 words 中的单词时，重置窗口；当窗口内某个单词数量过多时，也相应调整窗口左边界以保持合法性。