Leetcode daily question - 30 Concatenate substrings of all words

1. Title Description

30. Concatenate the substrings 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]

2. Problem solving ideas and codes

2.1 Their thinking

This problem needs to be in the string s The given... Was found in words Array of strings , The title requires several features ：

• words Each string in the string array has the same length
• words The string array needs to be in s Is continuous and occurs only once

According to these two characteristics , You can use a fixed length sliding window in s Traversal on , because words The string appears only once in , So the window length is words The sum of the lengths of all strings in the array . First, use a HashMap Statistics words The number of occurrences of each word in , Then the window s When sliding up, count the number of words in the window each time , If the word is in words There is no , Or there are more than words words Medium number , Exit the current window and go to the next window to continue judging . If the window is satisfied , Put the starting position in the result list and return . Here is an example 1 As an example .
s by “barfoothefoobarman”,words by {“foo”, “bar”}. stay words in foo once ,bar once , The length of a string is 3 ,words The total length of the string is 6 , So the window size is set to 6.

from s Start first , The window is 6 Then mark the angle from 0 To 5 To determine the character . At this time take 3 Characters get bar,bar stay words in , Record bar once , And the angle marks from 4 Begin to judge .

Take... Again at this time 3 Bit characters get foo ,foo stay words There are also , Record foo once . At this time, the statistics of the words in this window are completed , Return to the left edge of the window , And start counting the next window .

Get the word from the new window arf ,arf Not in words in , End the current window , Count the next window

Go through each window in turn , Until the string is overwritten s until

2.2 Code

class Solution {
    
    public List<Integer> findSubstring(String s, String[] words) {
    
        Map<String, Integer> wordsMap = new HashMap<>();
        int wordLength = words[0].length();
        int length = wordLength * words.length;
        for (int i = 0; i < words.length; i++) {
    
            wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);
        }
        List<Integer> ans = new ArrayList<>();
        outerLoop:
        for (int i = 0; i <= s.length() - length; i++) {
    
            Map<String, Integer> windowMap = new HashMap<>();
            int j = i;
            while (j <= i + length - wordLength) {
    
                String word = s.substring(j, j + wordLength);
                if (!wordsMap.containsKey(word)) {
    
                    continue outerLoop;
                }
                if (windowMap.getOrDefault(word, 0) + 1 > wordsMap.get(word)) {
    
                    continue outerLoop;
                }
                windowMap.put(word, windowMap.getOrDefault(word, 0) + 1);
                j += wordLength;
            }
            ans.add(i);
        }
        return ans;

    }
}

2.3 test result

Pass the test

3. summary

• Use HashMap Count the number of occurrences of strings in the array and in the window
• Use a fixed size window to traverse the string , And count the words in the window