30 Substring with Concatenation of All Words

30. Substring with Concatenation of All Words

1. Question

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.

For example, given: s:"barfoothefoobarman" words:["foo", "bar"]

You should return the indices:[0,9]. (order does not matter).

2. Implementation

(1) Two Pointers + Hash

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int n = words.length, wordLen = words[0].length();
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> seen = new HashMap<>();

        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i <= s.length() - wordLen * n; i++) {
            seen = new HashMap<>();
            int j = 0;

            for (; j < n; j++) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);

                if (!map.containsKey(word)) {
                    break;
                }

                seen.put(word, seen.getOrDefault(word, 0) + 1);
                if (seen.get(word) > map.get(word)) {
                    break;
                }
            }

            if (j == n) {
                res.add(i);
            }
        }
        return res;
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(mn), m为s的长度，n为words里word的个数，空间复杂度O(n)