LeetCode-30. Substring with Concatenation of All Words_leetcode 30. substring with concatenation of all w

前言

突然一周没刷过题了，有点时间就刷一下题吧，顺便把解题思路记录下来，一个是自己做笔记，一个是给大家一点思路。前面的二十多道以后有时间再补吧，现在刷到了30题，就从这个开始吧！

问题描述

解法一

首先是一种暴力解法，直接遍历所有可能的list，然后看这个list是否满足要求，在验证该list是否满足要求
的时候需要使用到类似hash的数据结构，保证words中的每个元素都被用到过一次，由于其中可能有重复
的元素，因此需要字典来保存这个元素重复的次数。

import copy
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if len(s) == 0:
            return []
        n = len(words)
        if n == 0:
            return []
        l = len(words[0])
        if l == 0 :
            return []
        ans = []
        d = {}
        for w in words:#保存到字典里
            if w not in d:
                d[w] = 1
            else:
                d[w] += 1               
        for k in range(len(s)-n*l+1):
            c = s[k:k+n*l] #遍历每一个可能的lsit
            dc = copy.deepcopy(d)
            count = 0
            for i in range(n):
                w = c[i*l:i*l+l]#遍历list中的每一个和word长度一样的子串 
                if w not in dc:#如果该子串不在words中则一定不符合条件 直接结束
                    break
                else:
                    if dc[w] >0:#如果当前还有相同的word没有被使用 则递减一
                        dc[w] -= 1
                        count += 1
                    else:#如果所有word都已经被用完 则也一定不符合条件 直接结束
                        break
           # print(count)
            if count == n:
                ans.append(k)
                #print(count)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

上面的代码写的很傻，中间还有一次内存拷贝，其实可以新建一个字典，然后比较两个字典是否相同即可。

解法二

下面是第二种解法:
主要思路是遍历s中的每一词，不断的把词放入字典中，然后判断字典是否满足条件。
设原来的words中构建的一个字典是d
键值是words中的word
value是word的个数
如 words = [“word”,“good”,“best”,“word”]
d[“word”] = 2
d[“good”] = 1
d[“best”] = 1
然后遍历s中所有可能的组成的词，已知words中的每一词的长度是固定的设为l，因此其组成的词的的下标为s[k:k+l]
此时会出现三种情况

• 这个词不在字典d中
  此时当前序列肯定不满足条件了，所以得从当前位置开始往后计算，并清空字典
• 这个词在字典d中，但是在dw中的个数超过了d中的个数
  此时不满足条件，所以需要把前面的某个词从词典中去掉，并修改当前开始位置
• 这个词既在字典中,也满足条件
  此时需要判断两个字典是否相同,如果相同则说明找到了一种情况了,记录下当前开始位置,继续向下找即可。

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if len(s) == 0:
            return []
        n = len(words)
        if n == 0:
            return []
        l = len(words[0])
        if l == 0 :
            return []
        ans = []
        d = {}
        for w in words:#保存到字典里
            if w not in d:
                d[w] = 1
            else:
                d[w] += 1  
            
        for k in range(l):
            begin = k
            dw = {}
            for j in range(begin,len(s),l):
                wk = s[int(j):int(j+l)]
                if wk not in d:#情况1 当前wk不在words中 则前面的都不会成立 
                    begin = j+l#开始值变为当前的值
                    dw.clear()#清空当前已有的字典
                else:
                    if wk not in dw:
                        dw[wk] = 1 #如果不在 则创建一个并赋值为1
                    else:
                        dw[wk] += 1   #如果在words中 则相应的值自加1
                    while dw[wk]>d[wk]:#情况2 如果当前的wk数量比words中的多 则找到满足条件的开始点
                        wt = s[int(begin):int(begin+l)]
                        dw[wt]-=1#将退出的单词减1
                        begin+=l#开始位置向后移动
                    #情况3 比原来的少 则比较当前是否为满足条件的字典
                    if dw == d:
                        ans.append(begin)#如果满足条件 则保存满足条件的起始位置    这里可以不用更改begin的位置 因为下面的循环 会自动进行修改   
        return list(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

总结

代码写的很烂，而且解释的也很迷。。。 就先将就着看吧，代码里面我尽量按照自己的想法进行了注释，如果有不懂的地方可以评论即可！