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 <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[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_countwords_freq = {}# 统计 words 中每个单词的频率for word in words:words_freq[word] = words_freq.get(word, 0) + 1result = []# 遍历所有可能的起始点 (最多 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 += 1else:# 如果频率超过要求，调整窗口，直到频率合法while window_freq[word] > words_freq[word]:left_word = s[left:left + word_len]window_freq[left_word] -= 1if window_freq[left_word] < words_freq[left_word]:count -= 1left += word_len# 如果窗口内匹配了所有单词，记录起始点if count == word_count:result.append(left)else:# 如果遇到无效单词，直接重置窗口window_freq.clear()count = 0left = rightreturn 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)# 输出60

2. 组合（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

感谢阅读，希望对你有所帮助~