30 Substring with Concatenation of All Words

Last Updated on: January 6, 2021 pm

30 Substring with Concatenation of All Words - Hard

Tags: HashMap, String

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

1
2
3
4
5
6
Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

1
2
3
4
Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution

参考链接

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        if(words.length == 0) return res;
        
        Map<String, Integer> map1 = new HashMap<String, Integer>();
        int wordNum = words.length;
        int wordLen = words[0].length();
        
        for(String str: words)
            map1.put(str,map1.getOrDefault(str, 0) + 1);
        
        
        for(int i = 0; i < s.length() - wordNum * wordLen + 1; i++){
            Map<String, Integer> map2 = new HashMap<String, Integer>();
            int curNum = 0;
            while(curNum < wordNum){
              String subWord = s.substring(i + curNum * wordLen, i + (curNum + 1) * wordLen);
                if(map1.containsKey(subWord)){
                    map2.put(subWord, map2.getOrDefault(subWord, 0) + 1);
                    if(map2.get(subWord) > map1.get(subWord))
                        break;
                }else
                    break;
                curNum ++;
            }
            if(curNum == wordNum)
                res.add(i);
        }
        return res;
    }
}