LeetCode link

Intuition

  • Build a set to store all the words
  • Iterate the slice index from 0 to end.
  • If all the words in the substring are appear once in the words, add the index to the result.

solution

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
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (words.length < 1 || s.length() < words.length) {
            return result;
        }
        int wordLength = words[0].length();
        if (s.length() < wordLength * words.length) {
            return result;
        }
        Set<String> set = new HashSet<String>(Arrays.asList(words));
        for (int i = 0; i <= s.length() - wordLength * words.length; i++) {
            int j = i;
            String word = s.substring(j, j + wordLength);
            while (set.contains(word)) {
                set.remove(word);
                j += wordLength;
                if (j + wordLength > s.length()) {
                    break;
                }
                word = s.substring(j, j + wordLength);
            }
            if (set.isEmpty()) {
                result.add(i);
            }
            set = new HashSet<String>(Arrays.asList(words));
        }
        return result;
    }
}

problem

WA.

reason

The words may be duplicate, so set is not proper to save the words.

modification

Change set to map

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
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (words.length < 1 || s.length() < words.length) {
            return result;
        }
        int wordLength = words[0].length();
        if (s.length() < wordLength * words.length) {
            return result;
        }
        Map<String, Integer> wordsMap = new HashMap<>();
        for (String word: words) {
            wordsMap.put(word, wordsMap.containsKey(word) ? wordsMap.get(word) + 1 : 1);
        }
        for (int i = 0; i <= s.length() - wordLength * words.length; i++) {
            int j = i;
            String word = s.substring(j, j + wordLength);
            Map<String, Integer> map = new HashMap<>(wordsMap);
            while (map.containsKey(word) && map.get(word) > 0) {
                int count = map.get(word);
                if (count <= 1) {
                    map.remove(word);
                } else {
                    map.put(word, count - 1);
                }
                j += wordLength;
                if (j + wordLength > s.length()) {
                    break;
                }
                word = s.substring(j, j + wordLength);
            }
            if (map.isEmpty()) {
                result.add(i);
            }
        }
        return result;
    }
}

promote

There’s a better solution using two pointer(sliding window), it’s similar with the Minimum Window Substring problem. Update after solve that one.