[Leetcode][python]Substring with Concatenation of All Words/与所有单词相关联的字串

秒速五厘米 2022-06-09 12:48 124阅读 0赞

## 题目大意 ##

现有一组长度相等的字符串words，要在原字符串中找出正好包含words中所有字符串的子字符串的起始位置。  
例子：  
输入: s = “barfoothefoobarman”, words = \[“foo”, “bar”\]  
输出: \[0, 9\]

## 解题思路 ##

考察哈希表和双指针两个知识点

因为words中的单词可能有重复，所以要有一个dict来记录一下每个字符串的数目。然后在遍历原字符串的时候，只需要遍历单词的长度次即可，如”barfoothefoobarman”，因为目标单词的长度为3，所以只需遍历：  
‘bar’ | ‘foo’ | ‘the’ | ‘foo’ | ‘bar’ | ‘man’  
‘arf’ | ‘oot’ | ‘hef’ | ‘oob’ | ‘arm’  
‘rfo’ | ‘oth’ | ‘efo’ | ‘oba’ | ‘rma’  
在遍历时，需要两个指针，一个用来标记子字符串的开始，另一个用来标记子字符串的结束。再用一个dict来记录当前字符串中单词的数量，如果下一个单词不在words中，那么清空该dict，把前指针直接跳到后指针处；如果在words中，那么相应的键值要加一，此时如果那个单词的数量超过了目标中的数目，那么前指针要不断后移直到吐出一个那个单词。通过前后指针之差是否等于所有目标单词长度之和来判断是否有目标子字符串。

参考：  
[https://shenjie1993.gitbooks.io/leetcode-python/030%20Substring%20with%20Concatenation%20of%20All%20Words.html][https_shenjie1993.gitbooks.io_leetcode-python_030_20Substring_20with_20Concatenation_20of_20All_20Words.html]

## 代码 ##

class Solution(object):
        def findSubstring(self, s, words):
            """
            :type s: str
            :type words: List[str]
            :rtype: List[int]
            """
            s_length = len(s)
            word_num = len(words)
            word_length = len(words[0])
            words_length = word_num * word_length
            result = []
            words_dict = {}
            for word in words:  # 将words中的词语加入words_dict，存在则+1，不存在则设为1
                words_dict[word] = words_dict[word] + 1 if word in words_dict else 1
            for i in range(word_length):  # 以单词长度为i的范围，例如长度为3，则为0,1,2位置分别开始遍历
                left = i
                right = i
                curr_dict = {}
                while right + word_length <= s_length:  # 右指针未超出s长度时
                    word = s[right:right + word_length]  # 提取word长度单词
                    right += word_length  # 右指针往后一个word长度
                    if word in words_dict:
                        curr_dict[word] = curr_dict[word] + 1 if word in curr_dict else 1  # 将本次遍历单词存入临时dict
                        while curr_dict[word] > words_dict[word]:  # 一旦临时dict中该单词数量大于本该有的数量，说明这一串匹配不成功
                            # 需要从最左边开始不断吐出单词，直到超过数量的单词，在这里while可以不断进入直到word这个单词的数量被减少
                            curr_dict[s[left:left + word_length]] -= 1  # 从左指针开始，逐个减去每个word出现的数量
                            left += word_length
                        if right - left == words_length:  # 如果子串长度和words长度相同，说明成功匹配
                            result.append(left)
                    else:  # 出现不在word中单词，清空临时dict，恢复指针
                        curr_dict.clear()
                        left = right
            return result

## 总结 ##

题目不难，但是逻辑需要理解

[https_shenjie1993.gitbooks.io_leetcode-python_030_20Substring_20with_20Concatenation_20of_20All_20Words.html]: https://shenjie1993.gitbooks.io/leetcode-python/030%20Substring%20with%20Concatenation%20of%20All%20Words.html