leetcode 30. 串联所有单词的子串 substring with concatenation of all words - python

目录

1. 解答
   1. 滑动窗口

https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

解答

滑动窗口

import collections
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words: return []
        i = 0
        ln = len(s)            # 原串多长
        n = len(words[0])      # 一个单词多长
        tar_count = len(words) # 目标一共有几个单词
        wc = collections.Counter(words)
        ans = []
        xx = set()
        while i <= ln - n:
            if s[i:i+n] in words and i % n not in xx:
                #print(s[i:i+n], 'start')
                xx.add(i%n)
                l = i
                r = i
                cur_wc = collections.Counter()
                cur_count = 0
                while r + n <= ln:
                    w = s[r:r+n]
                    if w not in wc:
                        l = r + n
                        r = r + n
                        cur_wc.clear()
                        cur_count = 0
                        #print('not in clear', w)
                        continue
                    else:
                        cur_wc[w] += 1
                        cur_count += 1
                        #print('add', w, cur_wc)
                        while cur_wc[w] > wc[w]:
                            nw = s[l:l+n]
                            cur_wc[nw] -= 1
                            l += n
                            cur_count -= 1
                        #print(cur_wc)
                        if cur_count == tar_count:
                            ans.append(l)
                    r += n
            i += 1
        return ans

不好理解的是为什么内层两个 for 循环只需要关注当前的这个单词 w。因为其实这里只需要保证 w 的个数是对的，就可以保证如果 cur_count == tar_count 时所有单词的数量都满足条件。所以无需判断其他单词的具体数量。