[LeetCode] Substring with Concatenation of All Words

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

思路：

和strStr那题的双指针解法类似。关键在于如何判断以任意i起始的S的substring是否整个L的concatenation。这里显然要用到hash table。由于L中可能存在重复的word，所以hash table的key = word，val = count of the word。

在建立好L的hash table后，对每个S[i]进行检查。这里的一个技巧建立一个新的hash table记录已经找到的word。因为L的hash table需要反复利用，不能被修改，并且如果以hash table作为参数进行值传递的化，时间空间消耗都很大。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> allPos; if(L.empty()) return allPos; int totalWords = L.size(); int wordSize = L[0].size(); int totalLen = wordSize * totalWords; if(S.size()<totalLen) return allPos; unordered_map<string,int> wordCount; for(int i=0; i<totalWords; i++) wordCount[L[i]]++; for(int i=0; i<=S.size()-totalLen; i++) { if(checkSubstring(S, i, wordCount, wordSize, totalWords)) allPos.push_back(i); } return allPos; } bool checkSubstring(string S, int start, unordered_map<string,int> &wordCount, int wordSize, int totalWords) { if(S.size()-start+1 < wordSize*totalWords) return false; unordered_map<string,int> wordFound; for(int i=0; i<totalWords; i++) { string curWord = S.substr(start+i*wordSize,wordSize); if(!wordCount.count(curWord)) return false; wordFound[curWord]++; if(wordFound[curWord]>wordCount[curWord]) return false; } return true; } };