LeetCode题解：30.串联所有单词的子串【Python题解超详细，KMP搜索、滑动窗口法】，知识拓展：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 <= 1041 <= words.length <= 50001 <= words[i].length <= 30words[i]和s由小写英文字母组成
解答
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
# # 思路一：KMP搜索法
# def prefix_table(pattern):
# m=len(pattern)
# prefix=[0]*m
# j=0
# for i in range(1,m):
# while j>0 and pattern[i]!=pattern[j]:
# j=prefix[j-1]
# if pattern[i]==pattern[j]:
# j+=1
# prefix[i]=j
# return prefix
# def kmp_search(pattern,text):
# m,n=len(pattern),len(text)
# prefix=prefix_table(pattern)
# j=0
# result=[]
# for i in range(n):
# while j>0 and text[i]!=pattern[j]:
# j=prefix[j-1]
# if text[i]==pattern[j]:
# j+=1
# if j==m:
# result.append(i+1-m)
# j=prefix[j-1]
# return result
# # 生成所有可能的串联子串
# all_patterns=set()
# for perm in permutations(words):
# all_patterns.add("".join(perm))
# result = []
# # 对每个可能的目标串进行 KMP 匹配
# for pattern in all_patterns:
# result.extend(kmp_search(pattern,s))
# return result
# 思路二：
if not s or not words:
return []
# 初始化变量
word_len = len(words[0])
word_count = len(words)
total_len = word_len * word_count
words_freq = {}
# 统计 words 中每个单词的频率
for word in words:
words_freq[word] = words_freq.get(word, 0) + 1
result = []
# 遍历所有可能的起始点 (最多 word_len 种不同的对齐方式)
for i in range(word_len):
left = i # 当前窗口的起始点
right = i # 当前窗口的结束点
window_freq = {}
count = 0 # 当前窗口内匹配的单词数
# 滑动窗口
while right + word_len <= len(s):
# 取出当前单词
word = s[right:right + word_len]
right += word_len
# 如果是有效单词
if word in words_freq:
window_freq[word] = window_freq.get(word, 0) + 1
# 如果频率不超过要求，增加匹配的单词数
if window_freq[word] <= words_freq[word]:
count += 1
else:
# 如果频率超过要求，调整窗口，直到频率合法
while window_freq[word] > words_freq[word]:
left_word = s[left:left + word_len]
window_freq[left_word] -= 1
if window_freq[left_word] < words_freq[left_word]:
count -= 1
left += word_len
# 如果窗口内匹配了所有单词，记录起始点
if count == word_count:
result.append(left)
else:
# 如果遇到无效单词，直接重置窗口
window_freq.clear()
count = 0
left = right
return result 思路一，KMP算法：该方法通过生成目标单词的所有排列，并利用 KMP 字符串匹配算法在目标字符串中寻找这些排列的匹配。KMP 算法通过预处理模式字符串，构建前缀函数来加速匹配过程，避免了暴力匹配中的重复计算。尽管 KMP 本身具有线性时间复杂度，但由于需要生成所有可能的单词排列，这使得该方法在多单词组合的情况下计算量大幅增加，导致整体效率不高。
思路二，滑动窗口法：滑动窗口法通过一个固定大小的窗口在目标字符串中滑动，窗口内的词频统计与目标单词集中的词频进行比较。如果匹配则记录窗口的起始位置，并通过调整窗口来维护频率的合法性。这种方法通过局部更新窗口内容，避免了对整个字符串的重新扫描，通常能够较为高效地处理多个单词的匹配，特别是在目标单词集合较大时具有较低的计算复杂度。
知识拓展： Python中的排列组合
在 Python 中，排列组合的计算通常可以借助 itertools 库进行实现，或者直接使用 math 库中的一些数学函数来进行相关的数学计算。下面将介绍一些常见的排列组合问题及其在 Python 中的实现方法。
1. 排列（Permutation）
排列是从一组元素中按照特定顺序选取元素。Python 中没有直接的排列函数，但可以使用 itertools.permutations 来生成排列。
import itertools
# 生成从列表 [1, 2, 3] 中选择 2 个元素的所有排列
arr = [1, 2, 3]
perms = itertools.permutations(arr, 2)
# 打印所有排列
for perm in perms:
print(perm)
# 输出为：
# (1, 2)
# (1, 3)
# (2, 1)
# (2, 3)
# (3, 1)
# (3, 2)
计算排列数：排列数可以通过 math 模块中的 factorial 函数来计算。
import math
# 计算从 5 个元素中选取 3 个的排列数
n = 5
k = 3
permutation_count = math.factorial(n) // math.factorial(n - k)
print(permutation_count)
# 输出602. 组合（Combination）
组合是从一组元素中选择元素，但不考虑顺序。Python 中可以使用 itertools.combinations 来生成组合。
import itertools
# 生成从列表 [1, 2, 3] 中选择 2 个元素的所有组合
arr = [1, 2, 3]
combs = itertools.combinations(arr, 2)
# 打印所有组合
for comb in combs:
print(comb)
# 输出：
# (1, 2)
# (1, 3)
# (2, 3)
计算组合数：组合数同样可以通过 math 模块中的 factorial 函数来计算。
import math
# 计算从 5 个元素中选取 3 个的组合数
n = 5
k = 3
combination_count = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
print(combination_count)
# 输出10感谢阅读，希望对你有所帮助~