Nuggets team number online, help you Offer impromptu! Click to view spring recruitment positions in big factories

I. Title Description:

Given a string s and some words of the same length. Find the starting position of the substring in S that happens to be formed by concatenating all the words in words.

Note that the substring must match exactly the words in words, without any other characters in the middle, but you do not need to consider the sequence in which words are concatenated.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting from index 0 and 9 are "barfoo" and "foobar", respectively. The order of the outputs is not important, [9,0] is also a valid answer.Copy the code

Example 2:

Input: s = "wordgoodGoodGoodBestWord ", words = ["word","good","best","word"]Copy the code

Subject address: leetcode-cn.com/problems/su…

Ii. Analysis of Ideas:

Slider, or window search. We define two Pointers, start and end. Our ultimate goal is to have exactly all the words from start to end, that is, all the words can be concatenated into a string from start to end.

When initialized, start and end both point to 0, define a count, and count the number of words in the window (start,end).

If end + word.length does not exceed s.length, there are other words available after end, and the loop begins

If s’s substring [end,end+word.length] is a word, then end moves to end+word.length, and the number of words increases by 1.

If count is equal to the total number of words, an answer has been found.

If the substring of s is not a word,end = start,end = start, the number of words is cleared.

Questions about repeating words:

Define two map collections, one for the original word and number mappings, and one for the word and number mappings of the slider window.

When moving end each time, judge whether the current number of words in the slide block exceeds the original number of words, move start if the number exceeds, and clear the temporary data

Iii. AC Code:

public List<Integer> findSubstring(String s, String[] words) { if(s.length() == 0 || words.length == 0){ return new ArrayList<>(); } Map<String,Integer> wordMap = new HashMap<>(); for (String word:words) { if (wordMap.containsKey(word)){ wordMap.put(word,wordMap.get(word)+1); }else { wordMap.put(word,1); } } Map<String,Integer> temp = new HashMap<>(); List<Integer> ans = new ArrayList<>(); int start = 0; int end = 0; int wordLength = words[0].length(); int arrLength = words.length; int tempArrLength = 0; while (end+wordLength<s.length()+1){ String tempWord = s.substring(end,end+wordLength); Integer value = wordMap.get(tempWord); Integer tempValue = temp.get(tempWord); if (value! =null&&(tempValue == null || tempValue<value)){ if (tempValue == null){ tempValue = 0; } temp.put(tempWord,tempValue+1); end+=wordLength; tempArrLength++; }else { start++; end = start; tempArrLength = 0; temp.clear(); } if (tempArrLength == arrLength){ ans.add(start); start++; end = start; tempArrLength = 0; temp.clear(); } } return ans; }Copy the code