30. Concatenate substrings of all words

30. Concatenate the substrings of all words

Original title link ：https://leetcode.cn/problems/substring-with-concatenation-of-all-words/

Given a string s And some of the Same length 's words words . find s It happens that words The starting position of the substring formed by concatenation of all words in .

Pay attention to the relationship between the string and words The words in match exactly , No other characters in the middle , But there's no need to think about words The order in which words are concatenated .

Example 1：

Input ：s = “barfoothefoobarman”, words = [“foo”,“bar”]
Output ：[0,9]
explain ：
From the index 0 and 9 The first substrings are “barfoo” and “foobar” .
The order of output is not important , [9,0] It's also a valid answer .
Example 2：

Input ：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
Output ：[]
Example 3：

Input ：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
Output ：[6,9,12]

Their thinking ：

stay s Start searching with the window size words Whether all the words of are included , Is continuous and used up .

Code implementation ：

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        #  Statistics words The words and their numbers in 
        words_dict = {
    }
        for word in words:
            words_dict[word] = words_dict.get(word, 0) + 1

        # words The length of the word , The explanation is that each word is the same length 
        word_len = len(words[0])
        #  The length of the window : The number of words  *  Word length 
        windows_len = len(words) * word_len
        #  Given string length 
        s_len = len(s)
        ans = []

        #  In the size of the window , In string s Search for ,i Is the starting point of each window 
        for i in range(s_len - windows_len + 1):
            #  Every time you use a statistical Dictionary , And you need to reduce the number to verify whether it meets the requirements of the topic 
            #  So use words_dict Shallow copy , Recycling , The equal sign refers to the same memory address 
            # deepcopy It's a deep copy , Parent independent , Child objects do not change , And you need to import import copy
            temp_dict = words_dict.copy()
            # j It is the end of a word in each window 
            j = i + word_len
            
            #  If s Found the string in words One of the words in , And the count in the dictionary is greater than 0 Words （ It means it hasn't been used up ）
            while s[j - word_len : j] in temp_dict and temp_dict[s[j - word_len : j]] > 0:
                #  Count of currently used words minus 1
                temp_dict[s[j - word_len : j]] -= 1
                #  Start next word position 
                j += word_len
            
            #  If the i Is the starting point and the words in the window are words_dict in , Then it meets the conditions 
            if sum(temp_dict.values()) == 0:
                ans.append(i)
        
        return ans

reference ：
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/solution/san-chong-fang-fa-zhu-jian-you-hua-by-hardcandy/