6.22 - hard - 5

30. Substring with Concatenation of All Words

朴素的挨个检查的方法TLE了

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        if not words:
            return []
        l = len(words[0])
        h = {}
        for w in words:
            if w in h:
                h[w] += 1
            else:
                h[w] = 1
        
        res = []
        total_l = l * len(words)
        for i in range(len(s) - total_l+1):
            j = i
            h_copy = copy.deepcopy(h)
            while s[j:j+l] in h_copy:
                if h_copy[s[j:j+l]] >= 1:
                    h_copy[s[j:j+l]] -= 1
                else:
                    break
                j += l
                if j - i == total_l:
                    res.append(i)
        return res

然后看了答案，仔仔细细把这道题又重写了一遍，发现其实就是一道dynamic window的问题，自己仔细的体会了一下，感觉对这种dynamic window的题目又加深了不少的理解

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        result = []
        if not words or len(s) < len(words) * len(words[0]):
            return result
        wl, total_length, n, word_dict = len(words[0]), len(words)*len(words[0]), len(s), {}
        # init word_dict
        for w in words:
            word_dict[w] = word_dict.get(w, 0) + 1
        
        # loop i here mean if there is a reslut index, then the result index must be i + m*wl, m is [0,1,2,3,4...]
        for i in range(wl):
            # it is a dynamic length window problem here
            # init the left boundary and tmp_dict
            left, tmp_dict = i, {} 
            for j in range(i, n-wl+1, wl): 
                # for each string, right boundary is fixed j+wl, only thing to consider is to shrink left boundary or not
                str = s[j: j+wl]
                right = j+wl
                if word_dict.get(str):
                    tmp_dict[str] = tmp_dict.get(str,0) + 1
                    # if current tmp_dict is not valid, keep moving the left boundary until it is valid
                    while tmp_dict[str] > word_dict[str]:
                        tmp_dict[s[left: left+wl]] -= 1 
                        left += wl                       
                    
                    # if the window length equals to result length
                    if right - left == total_length:
                        result.append(left)
                        # shrink the window by moving the left to right with wl 
                        tmp_dict[s[left: left+wl]] -= 1
                        left += wl
                else:
                    # if current str not in word_dict, then move left to next j
                    left, tmp_dict = j+wl,{}
        return result