LeetCode 30 Substring with Concatenation of All Words

Posted on | In | 阅读

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

利用滑动窗口搜索的方式

  • 计算每个word在words中出现的次数

  • 设置窗口，l为窗口左端点，r为窗口右端点，左闭右开，window记录窗口中每个单词的数量wordmap

    从0~len(word)-1开始枚举左端点的起点

    1. 扩展窗口，r不断的右移一个len(word)
      • 如果当前最右边的单词不在words中，则清理窗口 l = r
      • 如果在，window[word] += 1
        • window[word] < wordmap[word]继续扩展
        • window[word] == wordmap[word]检查是不是一个解，即r-l == len(word)*len(words)
        • window[word] > wordmap[word]进入步骤2
    2. 收缩窗口，l不断右移一个len(word)，window[l] -= 1，检查window[s[r-len:r]] == wordmap[s[r-len:r]]
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
class Solution:
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        wordmap = {}
        res = []
        if s == None or len(words) == 0:
            return res
        wordLen = len(words[0])
        for word in words:
            if wordmap.__contains__(word):
                wordmap[word] += 1
            else:
                wordmap[word] = 1
                
        for i in range(wordLen):
            window = {}
            l = r = i
            while r < len(s):
                while r < len(s):
                    word = s[r:r+wordLen]
                    r += wordLen
                    if word not in words:
                        window = {}
                        l = r
                    else:
                        if window.__contains__(word):
                            window[word] += 1
                        else:
                            window[word] = 1
                        if window[word] >= wordmap[word]:
                            break
                while l < r:
                    word = s[r-wordLen: r]
                    if window[word] == wordmap[word]:
                        break
                    tmpWord = s[l : l+wordLen]
                    window[tmpWord] -= 1
                    l += wordLen
                if r-l == wordLen*len(words):
                    res.append(l)
        return res