LeetCode 串联所有单词的子串 - 算法解析与代码实现

LeetCode 串联所有单词的子串 - 算法解析与代码实现

题目描述：

给定一个字符串 's' 和一些长度相同的单词 'words'，找出 's' 中恰好可以由 'words' 中所有单词串联形成的子串的起始位置。

注意子串要与 'words' 中的单词完全匹配，中间不能有其他字符，但不需要考虑 'words' 中单词串联的顺序。

示例 1：

输入：
s = 'barfoothefoobarman',
words = ['foo','bar']
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 'barfoo' 和 'foobar' 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：
s = 'wordgoodgoodgoodbestword',
words = ['word','good','best','word']
输出：[]

解题思路：

1. 字典统计： 首先我们需要先将 'words' 中的所有单词存储在一个字典 'word_dict' 中，以单词为 key，出现次数为 value。
2. 子串枚举： 然后我们需要枚举 's' 中的所有子串，判断该子串是否由 'words' 中的所有单词串联形成。
3. 子串划分： 具体做法是，我们将子串按 'words' 中单词的长度进行划分，并将划分后的每个子串与 'word_dict' 进行比较。4. 次数校验： 如果该子串在 'word_dict' 中出现的次数小于等于需要出现的次数，则说明该子串符合条件。5. 结果存储： 最后将符合条件的子串的起始位置存储在结果列表中即可。

代码实现：

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words: # 特判
            return []

        word_dict = {}
        for word in words: # 将 words 中的所有单词存储在 word_dict 中
            word_dict[word] = word_dict.get(word, 0) + 1

        word_len = len(words[0])
        total_len = len(words) * word_len
        res = []

        for i in range(len(s) - total_len + 1): # 枚举 s 中的所有子串
            temp_dict = {} # 存储当前子串中的所有单词出现的次数
            j = 0
            while j < total_len: # 将子串按单词长度进行划分，并统计每个单词的出现次数
                word = s[i+j:i+j+word_len]
                if word not in word_dict: # 如果该单词不在 word_dict 中，则说明该子串不符合条件
                    break
                temp_dict[word] = temp_dict.get(word, 0) + 1 # 统计该单词出现的次数
                if temp_dict[word] > word_dict[word]: # 如果该单词出现的次数大于需要出现的次数，则说明该子串不符合条件
                    break
                j += word_len
            if j == total_len: # 如果该子串符合条件，则将其起始位置存储在结果列表中
                res.append(i)

        return res

优化技巧：

• 使用字典统计单词出现次数，可以快速判断子串是否符合条件。
• 使用循环枚举子串，可以有效降低时间复杂度。
• 通过判断子串长度是否等于单词长度的总和，可以进一步优化代码。

希望本文对您理解和解决此 LeetCode 问题有所帮助。如果您有任何问题或建议，欢迎在评论区留言！