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).
?
?
?
算法1
?
暴力解法，从字符串s的每个位置都判断一次（如果从当前位置开始的子串长度小于L中所有单词长度，不用判断），从当前位置开始的子串的前段部分能不能由集合L里面的单词拼接而成。
?
从某一个位置 i 判断时，依次判断单词s[i,i+2], s[i+3,i+5], s[i+6, i+8]…是否在集合中，如果单词在集合中，就从集合中删除该单词。
?
我们用一个hash map来保存单词，这样可以在O(1)时间内判断单词是否在集合中
?
算法的时间复杂度是O（n*(l*k)）n是字符串的长度，l是单词的个数，k是单词的长度
?
?
?
递归代码如下：
?
class Solution {
private:
? ? int wordLen;
? ? ?
public:
? ? vector findSubstring(string S, vector &L) {
? ? ? ? unordered_mapwordTimes;
? ? ? ? for(int i = 0; i < L.size(); i++)
? ? ? ? ? ? if(wordTimes.count(L[i]) == 0)
? ? ? ? ? ? ? ? wordTimes.insert(make_pair(L[i], 1));
? ? ? ? ? ? else wordTimes[L[i]]++;
? ? ? ? wordLen = L[0].size();
? ? ? ? ?
? ? ? ? vector res;
? ? ? ? for(int i = 0; i <= (int)(S.size()-L.size()*wordLen); i++)
? ? ? ? ? ? if(helper(S, i, wordTimes, L.size()))
? ? ? ? ? ? ? ? res.push_back(i);
? ? ? ? return res;
? ? }
?
? ? //判断子串s[index...]的前段是否能由L中的单词组合而成
? ? bool helper(string &s, const int index,?
? ? ? ? unordered_map&wordTimes, const int wordNum)
? ? {
? ? ? ? if(wordNum == 0)return true;
? ? ? ? string firstWord = s.substr(index, wordLen);
? ? ? ? unordered_map::iterator ite = wordTimes.find(firstWord);
? ? ? ? if(ite != wordTimes.end() && ite->second > 0)
? ? ? ? {
? ? ? ? ? ? (ite->second)--;
? ? ? ? ? ? bool res = helper(s, index+wordLen, wordTimes, wordNum-1);
? ? ? ? ? ? (ite->second)++;//恢复hash map的状态
? ? ? ? ? ? return res;
? ? ? ? }
? ? ? ? else return false;
? ? }
};
?
?
非递归代码如下：
?
?
class Solution {
private:
? ? int wordLen;
? ? ?
public:
? ? vector findSubstring(string S, vector &L) {
? ? ? ? unordered_mapwordTimes;
? ? ? ? for(int i = 0; i < L.size(); i++)
? ? ? ? ? ? if(wordTimes.count(L[i]) == 0)
? ? ? ? ? ? ? ? wordTimes.insert(make_pair(L[i], 1));
? ? ? ? ? ? else wordTimes[L[i]]++;
? ? ? ? wordLen = L[0].size();
? ? ? ? ?
? ? ? ? vector res;
? ? ? ? for(int i = 0; i <= (int)(S.size()-L.size()*wordLen); i++)
? ? ? ? ? ? if(helper(S, i, wordTimes, L.size()))
? ? ? ? ? ? ? ? res.push_back(i);
? ? ? ? return res;
? ? }
? ? ?
? ? //判断子串s[index...]的前段是否能由L中的单词组合而成
? ? bool helper(const string &s, int index,?
? ? ? ? unordered_mapwordTimes, int wordNum)
? ? {
? ? ? ? for(int i = index; wordNum != 0 && i <= (int)s.size()-wordLen; i+=wordLen)
? ? ? ? {
? ? ? ? ? ? string word = s.substr(i, wordLen);
? ? ? ? ? ? unordered_map::iterator ite = wordTimes.find(word);
? ? ? ? ? ? if(ite != wordTimes.end() && ite->second > 0)
? ? ? ? ? ? ? ? {ite->second--; wordNum--;}
? ? ? ? ? ? else return false;
? ? ? ? }
? ? ? ? if(wordNum == 0)return true;
? ? ? ? else return false;
? ? }
};
?
?
OJ递归的时间小于非递归时间，因为非递归的helper函数中，hash map参数是传值的方式，每次调用都要拷贝一次hash map，递归代码中一直只存在一个hash map对象
?
算法2
?
回想前面的题目：LeetCode:Longest Substring Without Repeating Characters 和 LeetCode:Minimum Window Substring ，都用了一种滑动窗口的方法。这一题也可以利用相同的思想。
?
比如s = “a1b2c3a1d4”L={“a1”,“b2”,“c3”，“d4”}
?
窗口最开始为空，
?
a1在L中，加入窗口 【a1】b2c3a1d4 ? ? ? ? ? ? ? ? ? ? ? ? ? ?本文地址
?
b2在L中，加入窗口 【a1b2】c3a1d4
?
c3在L中，加入窗口 【a1b2c3】a1d4
?
a1在L中了，但是前面a1已经算了一次，此时只需要把窗口向右移动一个单词a1【b2c3a1】d4
?
d4在L中，加入窗口a1【b2c3a1d4】找到了一个匹配
?
如果把s改为“a1b2c3kka1d