Leetcode 50 day question brushing plan (day 3 - concatenate substrings of all words 10.00-13.20)

Tips ： When the article is finished , Directories can be generated automatically , How to generate it, please refer to the help document on the right

---

Preface

Writing difficult problems or overestimating oneself harm

One 、 Title Description

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

Two 、 Ideas

At present, the solutions to the problems we understand are all fixed window lengths , Slide one letter at a time , Divide the window string according to the fixed length of words , Then use the hash table to count the number of words after segmentation , Compare with the hash table maintained in advance
My initial idea was to use a longer window , Slide forward every time the comparison fails or a problem occurs , But it's too delicious. Many details are not clear now I hope I can come back and finish this one day
In the future, I'll focus on medium questions The difficult question is really meow. I don't want to touch it anymore QAQ

3、 ... and 、 Code

1. Code in question （python）

from collections import Counter

class Solution(object):
    def findSubstring(self, s, words):
        """ :type s: str :type words: List[str] :rtype: List[int] """
        # This problem is solved by sliding window , But the window movement size is the word length 
        move=len(words[0])

        # Maintain one hash surface 
        count=Counter(words)

        # Place the hash surface 
        cur=Counter()
        for i in list(count.keys()):
            cur[i]=0
       
        # Pointer to the front of the window 
        front=0
        # Return results 
        return_list=[]
        # Move  【 Let's assume that the string is exactly an integer multiple of the length 】
        for i in range(len(s)//move):
            # This round of words 
            temp=s[i*move:(i+1)*move]
            print(temp)#######
            # You need to ensure that this word is in the list 
            if(temp not in words):
                front+=move
                continue
            # First move the window to the appropriate position , So that this round of words can be inserted 
            while(cur[temp] >= count[temp]):
                if(front+move<len(s)): 
                    cur[s[front:(front+move)]]-=1
                    front+=move
                print(cur)#######
            # Insert this round of words 
            cur[temp]+=1
            print(cur)#######
            # Meet the length requirements after insertion , Add a return value 
            if(self.judge(count,cur)):
                return_list.append(front)
                print(return_list)######
        return return_list
    
    # Determine whether the two hash tables are the same 
    def judge(self,count,cur):
        flag=0
        for i in list(count.keys()):
            if(count[i]!=cur[i]):
                flag=1
                break
        if(flag != 1):
            return True
        else:
            return False

a=Solution()
a.findSubstring("barfoothefoobarman", ["foo","bar"])

2.python Of AC

class Solution(object):
    def findSubstring(self, s, words):
        """ :type s: str :type words: List[str] :rtype: List[int] """
        # Fixed length sliding window is used to solve this problem , The window size is the word length *word Number of words in 
        n=len(s)
        word_size=len(words[0])
        win_size=word_size*len(words)
        return_list=[]

        # Maintain one hash surface 
        count=Counter(words)

        # To traverse the 
        for i in range(len(s)-win_size+1):
            # This round of window string 
            win=s[i:(i+win_size)]
            # The word list after this round of segmentation （ Then make it hash surface ）
            cur=[]
            # Generate list 
            for j in range(0,win_size,word_size):
                cur.append(win[j:j+word_size])
            # Generate hash Table and comparison 
            if Counter(cur) == count:
                return_list.append(i)
        return return_list