python leetcode 30. Substring with Concatenation of All Words_python letcode30

这里判断是子字符串所以不用最小滑动窗而用DFS也能通过，每次都是从头判断。有几个剪枝点：

1.满足子字符串定长

2.字典中每个字符串定长

3.字典判断，dp1数组判断是否满足跳出循环条件

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if words==[]: return []
        res=[]
        adict={}
        l=len(words[0])
        count=len(words)
        ls=len(s)
        dp1=[0]*count
        for index in range(count):
            ws=words[index]
            if ws in adict:
                index=adict[ws]
            else:
                adict[ws]=index
            dp1[index]+=1
        for i in range(len(s)-l*count+1):
            curl=i
            dp=dp1[:]
            while curl+l<=ls and s[curl:curl+l] in adict:
                index=adict[s[curl:curl+l]]
                dp[index]-=1
                if dp[index]<0:
                    break 
                curl+=l
            if curl-i==count*l:
                res.append(i)
        return res
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