Problem description:

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 = "wordgoodstudentgoodword",
  words = ["word","student"]
Output: []

Solution:

Use two hash table.

  1. First hash table, map, stores every words.
  2. Second hash table, seen, determine if a substring is in the map or not. If the substring is not in the map, it means the substring is not a word in given words. In addition, it can only appear once in current search, so if the count in seen is greater than in the map, we should break the loop.
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
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        
        vector<int> res;
        if(s.empty() || words.empty()) return res;
        unordered_map<string, int> map;
        for(string word: words)
            map[word]++;
        
        int n= s.length(), num= words.size(), len= words[0].length();
        
        for(int i= 0; i< n- num*len+1; i++){
            unordered_map<string, int> seen;
            int j= 0;
            for(; j< num; j++){
                string word= s.substr(i+j*len, len);
                if(map.find(word) != map.end()){
                    seen[word]++;
                    if(seen[word]> map[word])
                        break;
                }
                else
                    break;
            }
            if(j == num) res.push_back(i);
        }
        return res;

    }
};

time complexity: $O(n*num)$
space complexity: $O(words.size())$
reference:
https://goo.gl/wy6wAq
https://goo.gl/MAkUfJ