Skip to content

030 Substring with Concatenation of All Words

30. Substring with Concatenation of All Words

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

难度 : Hard

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        res = []
        if len(words) == 0 or len(s) < len(words) * len(words[0]):
            return res
        n, m, wl = len(s), len(words), len(words[0])
        maps, cur_map = {}, {}
        maps = collections.Counter(words)
        for i in range(wl):
            count, start, r = 0, i, i
            while r + wl <= n:
                string = s[r:r+wl]
                if string in maps:
                    cur_map[string] = cur_map.get(string, 0) + 1     
                    if cur_map[string] <= maps[string]:
                        count += 1
                    while cur_map[string] > maps[string]:
                        tmp = s[start:start+wl]
                        cur_map[tmp] -= 1
                        start += wl
                        if cur_map[tmp] < maps[tmp]:
                            count -= 1
                    if count == m:
                        res.append(start)
                        tmp = s[start:start+wl]
                        cur_map[tmp] -= 1
                        start += wl
                        count -= 1
                else:
                    cur_map = {}
                    count = 0
                    start = r + wl
                r += wl
            cur_map = {}
        return res




回到顶部