Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
45 lines (41 sloc) 1.46 KB
problem:
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
--------------------------------------------
solution:
//一拿到这个题,容易一点思路也没有,但由于在L中所有的word长度相同,因此在取字符串上方便很多
//string和map结合使用,substr, find, at
//要考虑到L中可能有重复的单词,所以用map而不是set,有个数量的问题
vector<int> findSubstring(string S, vector<string> &L)
{
map<string, int> word; //放L中所有的字符串,此题的特点是这些字符串等长
map<string, int> curStr;
vector<int> ret;
int N = L.size();
if(N <= 0)
return ret;
for(int i = 0; i < L.size(); i++)
++word[L.at(i)];
int M = L.at(0).size();
int i, j;
for(i = 0; S.size() >= N * M &&i <= S.size() - N * M; i++) //这里有个坑,如果S.size() - N * M小于0,得到的实际上是一个很大的数,循环不会停止而一直继续
{
curStr.clear();
for(j = 0; j < N; j++)
{
string t = S.substr(i + j * M, M);
if(word.find(t) == word.end()) //没找到时
break;
++curStr[t];
if(curStr[t] > word[t]) //数量不对时
break;
}
if(j == N)
ret.push_back(i);
}
return ret;
}