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).
Solution: similar to obtain the statistics of numbers of words in hash table.
1 class Solution { 2 public: 3 vector<int> findSubstring(string S, vector<string> &L) { 4 vector<int> res; 5 if (S.empty() || L.empty()) return res; 6 int M = S.size(), N = L.size(); 7 int K = L[0].size(); 8 unordered_map<string, int> need; 9 unordered_map<string, int> found; 10 for (int i = 0; i < N; ++i) 11 need[L[i]]++; 12 for (int i = 0; i <= M - N * K; ++i) { 13 found.clear(); 14 int j; 15 for (j = 0; j < N; ++j) { 16 string s = S.substr(i + j * K, K); 17 auto it = need.find(s); 18 if (it == need.end()) 19 break; 20 if (it->second <= found[s]) 21 break; 22 found[s]++; 23 } 24 if (j == N) res.push_back(i); 25 } 26 return res; 27 } 28 };
Substring with Concatenation of All Words,布布扣,bubuko.com
Substring with Concatenation of All Words
原文：http://www.cnblogs.com/zhengjiankang/p/3682061.html