This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022.

A substring that concatenates all the words

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 at index 0 and 9 are “barfoo” and “foobar” respectively. The order of the outputs is not important, [9,0] is 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]

Tip:

  • 1 <= s.length <= 104
  • S consists of lowercase letters
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • Words [I] consists of lowercase English letters

Answer:

Sliding window + hash table

1. Two hashMaps are used:

  • Map is used to record the number of occurrences of words. Key is the value of each element in wards and value is the number of occurrences of the current element. We can use this to access and modify the map valuegetOrDefault(w, 0)Method, set a default value of 0. Avoid simple logic problems such as NPE
  • SubMap is used to record the number of occurrences of the word in the substring (in the sliding window), and if the substring is found within one period of the condition, or if it is not found, it will be reset.

Here’s a picture:

2. WordLen is the number of wordswords.length“OneLen” is the length of a wordwords[0].length

3. Iterate over the string, moving the length tooneLen+ wordLenIs the sum of all the character lengths in the words array. Compare each sliding window in turn in the sliding window. The maximum value of the slide coordinates is zeros.length - (oneLen * wordLen + 1) .

4. When the window appears, any word in words is not matched or the number of matches exceeds the maximum number. So this sliding window does not meet, directlybreakGo to the next slide window for matching.

5. If the match is complete, add the starting coordinates of the sliding window to the result, and finally walk through all the Windows to return the result.

Solution code:

code

The solution code is as follows:

class Solution { public List<Integer> findSubstring(String s, String[] words) { List<Integer> ans = new ArrayList<>(); / / to empty the if (words = = null | | words. The length = = 0 | | s = = null | | s.l ength () = = 0) {return ans. } // Initialize Map<String, Integer> Map = new HashMap<>(); int oneLen = words[0].length(); int wordLen = words.length; int allLen = oneLen * wordLen; If (s.length() < allLen) return ans; For (String w: words) {// No substring if (! s.contains(w)) return ans; map.put(w, map.getOrDefault(w, 0) + 1); } for (int i = 0; i < s.length() - allLen + 1; i++) { Map<String, Integer> subMap = new HashMap<>(); int idx = i; While (idx < I + allLen) {curWord = s.substring(idx, idx + oneLen); / / if there is no | | already exists and the number of matching enough if (! map.containsKey(curWord) || Objects.equals(subMap.get(curWord), map.get(curWord))) { break; } subMap.put(curWord, subMap.getOrDefault(curWord, 0) + 1); idx += oneLen; } if (idx == i + allLen) { ans.add(i); } } return ans; }}Copy the code

Time complexity: Assuming that the length of S is N and there are m words in words, the time complexity is O (n * m). Spatial complexity: Two Hashmaps, assuming m words in words, is O (m).

conclusion

Optimization thinking:

We’re moving one letter at a time in logic, but in the case of a perfect match, we can move one word because we’ve matched all the substrings that match. In addition, we can directly skip when there is a completely mismatched word, and when the number of times exceeds, we only need to remove the first repeated word, the final optimization time complexity can reach O(n), detailed implementation we can go to the reference for detailed implementation.

This is the first time to sort out the algorithm-related articles carefully. I hope I can continue to share and learn with you when I have time in the future.

References and citations

  • Leetcode-cn.com/problems/su…
  • leetcode.wang/
  • Leetcode. Wang/leetcode – 30…