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).
记S长度为n，每个单词word长度为len，字典L共有size个单词。
逐位扫描，以[0,n-len*size]分别作为起始点，判断后续的len*size个word是否正好是字典L中的word。
有一点加速细节需要注意：
判断某个元素word是否在map中，可以判断m[word]是否为0（int 的默认值），这样可以节省时间。
class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> ret; if(S == "" || L.empty()) return ret; int n = S.size(); int len = L[0].size(); int size = L.size(); map<string, int> m; //count the L[i] string, and accelerate the find process for(int i = 0; i < size; i ++) {//if L[i] not exists, map will create a pair with default value <L[i], 0> m[L[i]] ++; } for(int i = 0; i <= n-len*size; i ++) {//at least len*size for all the words //start from i map<string, int> curM = m; int j; int count = 0; for(j = i; j < i+len*size; j += len) {//try size words start from i string word = S.substr(j, len); if(curM[word] != 0) //word exists in L //curM.find(word) != curM.end() curM[word] --; else //not found or found enough break; } if(j == i+len*size) //matched until end ret.push_back(i); } return ret; } };
【LeetCode】Substring with Concatenation of All Words
原文：http://www.cnblogs.com/ganganloveu/p/4172752.html