Leetcode daily question - 30 Concatenate substrings of all words

subject

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

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]

Tips ：

1 <= s.length <= 104
s It's made up of lowercase letters
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] It's made up of lowercase letters

Ideas

This question means to find a given s Middle energy quilt words All characters in the string can be used once to form the starting subscript of the substring .

because words The length of Chinese characters is consistent , So I thought I could use sliding windows , The window length is words The length of Chinese characters n.

And you need a hash table record words Characters in and the number of occurrences , because words Characters in may be duplicated , You can't simply use an array to determine whether it exists .

The way to do it is , Maintain this sliding window , Determine whether the value in the window is words in

• If not , Direct left and right ends at the same time +1, The whole window moves one unit to the right .
• If in , The number of corresponding characters in the hash table -1, Slide the window once to the right n A unit of , Directly determine whether the characters in the next window are in the hash table , If step above the loop , Be careful ： The most important thing to judge here is words The length of the characters in , Because the title requires all characters to appear and appear once

Finally, judge whether all the values in the hash table are zero , If all are zero, record the left pointer of the sliding window , If it is not zero, the left and right ends shall be at the same time +1, The whole window moves to the right , Just repeat the above steps .

Answer key

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        n = len(words[0])
        #  Slide the pointers on both sides of the window 
        l, r = 0, n
        res = []
        temp = {}
        #  Hash table records characters and quantity 
        for i in words:
            temp[i] = temp.get(i, 0) + 1
        while r <= len(s):
            ans = copy.copy(temp)
       		#  The characters in the window exist in words
            if s[l:r] in words:
            	#  Each move n Unit judgment 
                for i in range(0, len(words)):
                    index = s[l+i*n:r+i*n]
                    if ans.get(index, 0) != 0:
                        ans[index] -= 1
                    else:
                        break
            if len(set(ans.values())) == 1 and list(ans.values())[0]==0:
                res.append(l)
            #  The whole window moves to the right 
            l += 1
            r += 1
        return res