leetcode/python_src/SubstringWithConcatenationOfAllWords.py at master · hooting/leetcode · GitHub

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
40
41
42
43
44
45
46
47
48
49
"""
 reference to https://leetcode.com/discuss/20151/an-o-n-solution-with-detailed-explanation
 given a sliding window with size lenW
 if the sliding window matches in s, then slide the window with step lenW
 else remove the previous matched window
"""
class Solution:
    # @param {string} s
    # @param {string[]} words
    # @return {integer[]}
    def findSubstring(self, s, words):
        dic = {}
        result = []
        for word in words:
            if word in dic: dic[word] += 1
            else: dic[word] = 1
        wordNum = len(words)
        lenW = len(words[0])
        lenS = len(s)
        for i in range(lenW):
            count = 0
            foundDic = {}
            left = i
            for j in range(i,lenS - lenW + 1,lenW):
                sub = s[j:j+lenW]
                if sub in dic:
                    count += 1
                    if sub in foundDic:
                        foundDic[sub] += 1
                    else:
                        foundDic[sub] = 1
                    while foundDic[sub] > dic[sub]:
                        removeSub = s[left:left+lenW]
                        foundDic[removeSub] -= 1
                        count -= 1
                        left += lenW
                    if count == wordNum:
                        result.append(left)
                        removeSub = s[left:left+lenW]
                        foundDic[removeSub] -= 1
                        count -= 1
                        left += lenW
                else:
                    count = 0
                    foundDic = {}
                    left = j + lenW
        return result