分类:algorithm| 发布时间:2016-08-07 21:48:00
You are given a string, s, and a list of 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).
给出一个字符串以及一组长度相同的单词,找出所有每个单词连接而成的字串的下标。
这种解法的基本思路是将给出的 words 中每个单词出现的次数放入一个 map 中。 然后取出给定的字符串的 num * len 个字符,分为 num 个单词, 将其出现的次数放入另一个 map 中,对比这两个 map 是否相同。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> counts;
for (const string &word: words) counts[word]++;
int n = s.length(), num = words.size(), len = words[0].length();
vector<int> indexes;
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 (counts.find(word) != counts.end()) {
seen[word]++;
if (seen[word] > counts[word])
break;
} else {
break;
}
}
if (j == num) indexes.push_back(i);
}
return indexes;
}
};
这个算法可以看成是上一个算法经过优化得到的。 首先,外层循环 i 从 0 到 wl。 相应地,内层循环以 wl 为单位处理整个字符串。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
int n = s.size(), cnt = words.size();
if (n <= 0 || cnt <= 0) return ans;
// init word occurence
unordered_map<string, int> dict;
for (int i = 0; i < cnt; ++i) dict[words[i]]++;
// travel all sub string combinations
int wl = words[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;
}
} else {
// not a valid word, reset all vars
tdict.clear();
count = 0;
left = j + wl;
}
}
}
return ans;
}
};