[LeetCode] 30. Substring with Concatenation of All Words

Posted on | In

Problem

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 "barfoor" 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: []

Explanation 1

  1. Create a hash table and store the words frequency.

  2. Loop through the string s, because we need to record the starting index, then we need to create a copy of the i index as tempInd. For example, get the substring bar and check if it is in the the hashmap.

  3. If the substring is not inside the hashmap, then we move the index i to the next index. If it is in the hashmap, then we subtract 1 from it’s frequency. If it’s frequency is 0, we can remove its key. Then tempInd += wordLen, and get the next substring foo and check if inside the hashmap, if it is, then do the same thing, reduce its frequncy, if its frequency is 0, remove its key.

  4. When the hashmap is empty, that means we found all words continuously, and we add the index i to the res list.

Solution 1

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
33
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s.length() == 0 || words.length == 0) return res;
        HashMap<String, Integer> hm = new HashMap<>();
        for (String str : words) {
            hm.put(str, hm.getOrDefault(str, 0)+1);
        }
        int strLen = s.length();
        int wordArrLen = words.length;
        int wordLen = words[0].length();
        for(int i = 0; i <= strLen - wordArrLen*wordLen; i++) {
            int tempInd = i;
            HashMap<String, Integer> tempHm = new HashMap<>(hm);
            
            while(tempInd + wordLen <= i+wordArrLen*wordLen) {
                String tempWord = s.substring(tempInd, tempInd+wordLen);
                if (!tempHm.containsKey(tempWord)) {
                    break;
                }
                tempHm.put(tempWord, tempHm.get(tempWord)-1);
                if (tempHm.get(tempWord) == 0) {
                    tempHm.remove(tempWord);
                }
                if (tempHm.isEmpty()) {
                    res.add(i);      
                }
                tempInd += wordLen;       
            }
        }
        return res;
    }
}

Explanation 2

  1. We can iterate word by word in this method. From example 1, each word has length 3, then the iteration order will be 0, 3, 6, 8, 12, 15, then moving one steps forward, 1, 4, 7, 9, 13, 16, then moving one steps forward, 2, 5, 8, 10, 14, 17. In this way, we can consider all cases.

  2. We need a hashmap hm to record the word frequency. Then, we starts from 0, using left to record the starting index, using count to check how many word we have matched so far, using tempHm to record the word frequency we have seen so far.

  3. Iterating word by word, if the word iterated is inside hm, then we put inside to tempHm. If the word frequency inside tempHm is less or equal to the frequency in hm, then we add one to the counter.

  4. If the word frequency inside tempHm is greater than frequency in hm. For example, s = barfoofoo, word = {bar, foo, abc}, when we iterate to the second foo in s, we have tempHm[foo] = 2, which is greater than hm[foo] = 1, and now the left is at index 0. Then, we need to move left pointing to the beginning of the next word, which is at index 3, and we need to remove the first word bar out of tempHm, which means we subtract its frequency by 1. After subtracting its frequency, if tempHm[bar] < hm[bar], that means we we lost 1 match, so we subtract counter by 1. Again, now the left is at index 3 pointing at the first foo in s. We know that 3 cannot be the correct starting index because foofoo doesn’t match word’s frequency. So, we move the left pointing to the next word, pointing to the second foo which at index 6, remove the first word foo out of tempHm, subtract its frequency by 1. Now, temp[foo] == hm[foo] and left is pointing to the correct index, and we contnue the loop.

  5. If count == words.length, then it means we successfully match all words continuously, and we store the left into res list. And we remove the first word from tempHm and subtract count by 1, and move the left to pointing at the next word, and continue the loop.

  6. If the word we iterated is not inside hm, for example, s = barxxxfoo, word = {bar, foo, abc} because xxx is not inside hm, we move the left to index 6 pointing to foo and we clear the tempHm and count.

Solution 2

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s.length() == 0 || words.length == 0) return res;
        HashMap<String, Integer> hm = new HashMap<>();
        for (String str : words) {
            hm.put(str, hm.getOrDefault(str, 0) + 1);
        }
        int wordLen = words[0].length();
        for (int i = 0; i < wordLen; i++) {
            int tempInd = i;
            int count = 0;
            int left = i;
            HashMap<String, Integer> tempHm = new HashMap<>();
            for (tempInd = i; tempInd <= s.length()-wordLen; tempInd+=wordLen) {
                String tempStr = s.substring(tempInd, tempInd+wordLen);
                if (hm.containsKey(tempStr)) {
                    tempHm.put(tempStr, tempHm.getOrDefault(tempStr, 0) + 1);
                
                    if (tempHm.get(tempStr) <= hm.get(tempStr)) {
                        count += 1;
                    } else {
                        while (tempHm.get(tempStr) > hm.get(tempStr)) {                    
                            String first = s.substring(left, left+wordLen);
                            tempHm.put(first, tempHm.get(first) - 1);
                            if (tempHm.get(first) < hm.get(first)) {
                                count -= 1;
                            }
                            left += wordLen;
                        }
                    }
                    if (count == words.length) {
                        res.add(left);
                        String tempFirst = s.substring(left, left+wordLen);
                        tempHm.put(tempFirst, tempHm.get(tempFirst)-1);
                        if (tempHm.get(tempFirst) < 1) tempHm.remove(tempFirst);
                        count -= 1;
                        left += wordLen;
                    }
                } else {
                    tempHm.clear();
                    count = 0;
                    left = tempInd + wordLen;
                }
            }
        }
        
        return res;
    }
}