leetcode：30. 串联所有单词的子串【Counter匹配 + 剪枝】

分析

用个Counter记录words的出现次数
然后记录总长度和每个单词的长度
开始对s的起点遍历
然后看看从s中截取的内容的Counter是否符合
一旦有某个超过就直接剪枝即可

ac code

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        # double pointers
        pattern = Counter(words)
        n, m, seg, nums = len(s), len(''.join(words)), len(words[0]), len(words)
        ans = []
        #print(pattern)

        for st in range(n - m + 1):
            now = s[st: st + m]
            c = Counter()
            flag = True
            for i in range(nums):
                c[now[seg*i : seg*(i + 1)]] += 1
                if c[now[seg*i : seg*(i + 1)]] > pattern[now[seg*i : seg*(i + 1)]]:
                    flag = False
                    break
            if not flag:
                continue
            #print(c)
            if c == pattern:
                ans.append(st)
        
        return ans

总结

简单Counter