【leetcode】串联所有单词的子串

我不是女神ヾ 2022-04-23 08:30 139阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]

## 算法思想 ##

遍历words，做出一个字典，然后再遍历s，将s后面words长度个单词做成一个字典，然后两个字典比较即可。  
注意字典的深拷贝

import copy
    class Solution:
        def findSubstring(self, s, words):
            """ :type s: str :type words: List[str] :rtype: List[int] """
            if s == '' or words == []:
                return []
            lenWord = len(words[0])
            times = { }
            results = []
            for word in words:
                if word in times:
                    times[word] += 1
                else:
                    times[word] = 1
            for i in range(len(s) - len(words) * lenWord + 1):  #遍历匹配
                j = 0
                times1 = copy.deepcopy(times)   #字典的深拷贝
                while j < len(words):   #在words中匹配
                    print(i, j)
                    startWord = i + j * lenWord   #单词开始
                    word = s[startWord:startWord+lenWord]
                    print(word)
                    if word not in times1:   #不匹配
                        break
                    times1[word] -= 1
                    if times1[word] < 0:
                        break
                    if j == len(words) - 1:
                        results.append(i)
                    j += 1
            return results

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220322/570bcd3ad6a44993987ccdb0aa8a412c.png