30 Substring with Concatenation of All Words
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).
Solution
class Solution {
public:
bool isValid(unordered_map<string, int> dict, string s, int ns) {
int n = s.size();
for ( int i = 0; i <= n-1; i += ns ) {
string word = s.substr(i, ns);
if ( dict.find(word) == dict.end() ) return false;
dict[word] -= 1;
if ( dict[word] == 0 ) dict.erase(dict.find(word));
}
return true;
}
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
int n = words.size();
if ( n == 0 ) return res;
int ns = words[0].size();
int len = s.size();
if ( len < n*ns ) return res;
unordered_map<string, int> dict;
for ( int i = 0; i <= n-1; i++ ) {
string word = words[i];
if ( dict.find(word) == dict.end() ) dict[word] = 1;
else dict[word] += 1;
}
for ( int i = 0; i <= len - n*ns; i++ ) {
if ( isValid(dict, s.substr(i, n*ns), ns) ) res.push_back(i);
}
return res;
}
};
Notes
Similar to the "DNA sequence problem". Note the use of hashtable.