首页 > 代码库 > 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