leetcode：30. Concatenate substrings of all words [counter matching + pruning]

analysis

Use one Counter Record words Number of occurrences of
Then record the total length and the length of each word
Began to s Start traversal of
Then look at the s Of the content intercepted in Counter Compliance
Once there is a certain excess, just prune it directly

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

summary

Simple Counter