首页 > 代码库 > leetcode第29题--Substring with Concatenation of All Words

leetcode第29题--Substring with Concatenation of All Words

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).

题目的意思是,给定S和字符串数组L,判断S中是否存在包含L中的所有字符串,字符串的顺序不做要求,但是字符串之间不得有其他字符,如果存在,返回S中的下标。例如“abcba”,L为“a”,“b”,那么返回0和3. 还有就是允许之间的重复,也就是“aba”,L为“a”,“b”时,返回为0和1,其中b被重复考虑。

做法是这样的,先创建两个map<string, int> 一个是用来计算L中每种串的出现次数。另外一个是用来在遍历过程中判断超出了第一个map表记录的L中的次数。第二个map记得每次重新遍历的时候要清空。详细代码如下:

class Solution {public:vector<int> findSubstring(string S, vector<string> &L){    vector<int> ans;    if (S.size() == 0 || L.size() == 0 || S.size() < L.size() * L[0].size())        return ans;     int wordNum = L.size();    int wordLen = L[0].size();    int searchEnd = S.size() - wordNum * wordLen;    map<string, int> total;    map<string, int> subMap;        for(int i = 0; i < wordNum; i++)    {        total[L[i]]++;    }        for (int i = 0; i <= searchEnd; i++) // 等号不能少了,还有最后就是用searchEnd代替S.size() - wordNum*wordLen;    {        int matchNum = 0, j = i;        subMap.clear();// 记得清空        for (; matchNum < wordNum; matchNum++)        {            string subs = S.substr(j, wordLen);            if (total[subs] == 0)                break;            if (++subMap[subs] > total[subs])                break;            j += wordLen;        }        if (matchNum == wordNum)            ans.push_back(i);    }    return ans;}};

还可以参见http://www.tuicool.com/articles/Uza2eui;java的参见http://blog.csdn.net/linhuanmars/article/details/20342851这个方法比较快,有时间一定要学学。

leetcode第29题--Substring with Concatenation of All Words