Участник:F.Nikitin/FindSubstring

Ссылки сюда (2) →

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

from collections import Counter
 
class Solution:
    def findSubstring(self, s, words):
        res = []
        if len(words) == 0: return res
 
        word2count = dict(Counter(words))
        n, m, k = len(s), len(words[0]), len(words) 
 
        for i in range(n - m * k + 1):
            flag = True
            tmp = {}
 
            for j in range(k):
                word = s[i + m * j:i + m * j + m]  
                if word not in word2count:  
                    flag = False
                    break
                tmp[word] = tmp.get(word, 0) + 1
 
                if tmp[word] > word2count[word]:
                    flag = False
                    break
            if flag: res.append(i)
        return res