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 wordsexactly 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).
解题思路:
(1) 怎样得到所有候选解?
一种方法是用大小为words.size()*words[0].size()的window在s上滑动选取候选集,即得到的候选集为:barfoo,arfoot,rfooth... 等等.然后对候选解处理,判断是否是一个concatenation。
另一种方法的思想是:通过words[0].size()次移位覆盖所有候选集,具体思想是:
方法二:引入变量left,假设left = 0,即从第0个元素起开始处理,遍历每个单词,形式为:bar foo the foo bar man; left = 1时,遍历每次单词,为:arf oot hef oob arm; left=2时,遍历每个单词,形式为:rfo oth efo oba rma. 当left>=word[0].size()= 3时,单词的划分形式和left=1相同。因此,上述三种划分覆盖了所有的单词划分形式。而每个候选解即是这些单词的顺序组合。
(2) 怎样判断候选解?
对words建立一个词典,对s建立一个词典,比较s的词典和words中的词典是否吻合,若是,则找到一个符合条件的解。
方法二代码:
class Solution {
public:
// travel all the words combinations to maintain a window
// there are wl(word len) times travel
// each time, n/wl words, mostly 2 times travel for each word
// one left side of the window, the other right side of the window
// so, time complexity O(wl * 2 * N/wl) = O(2N)
vector<int> findSubstring(string S, vector<string> &L) {
vector<int> ans;
int n = S.size(), cnt = L.size();
if (n <= 0 || cnt <= 0) return ans;
// init word occurence
unordered_map<string, int> dict;
for (int i = 0; i < cnt; ++i) dict[L[i]]++;
// travel all sub string combinations
int wl = L[0].size();
for (int i = 0; i < wl; ++i) {
int left = i, count = 0;
unordered_map<string, int> tdict;
for (int j = i; j <= n - wl; j += wl) {
string str = S.substr(j, wl);
// a valid word, accumulate results
if (dict.count(str)) {
tdict[str]++;
if (tdict[str] <= dict[str])
count++;
else {
// a more word, advance the window left side possiablly
while (tdict[str] > dict[str]) {
string str1 = S.substr(left, wl);
tdict[str1]--;
if (tdict[str1] < dict[str1]) count--;
left += wl;
}
}
// come to a result
if (count == cnt) {
ans.push_back(left);
// advance one word
tdict[S.substr(left, wl)]--;
count--;
left += wl;
}
}
// not a valid word, reset all vars
else {
tdict.clear();
count = 0;
left = j + wl;
}
}
}
return ans;
}
};
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
int sz = s.size();
int n = words.size();
if(!sz || !n) return ans;
int l = words[0].size();
int t_size = n*l;
unordered_map<string,int> t_map;
for(auto c:words){
t_map[c]++;
}
int start = 0;
while(start+t_size<=sz){
unordered_map<string,int> s_map;
int count=0;
for(int i=start;i<t_size+start;i+=l){
string c = s.substr(i,l);
if(t_map[c]>0){
++s_map[c];
if(s_map[c]==t_map[c]) count+=t_map[c];
else if(s_map[c]>t_map[c]) break;
}
else break;
}
if(count==n) ans.push_back(start);
start++;
}
return ans;
}
};