首页 > 代码库 > Substring with Concatenation of All Words
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).
分析：brute-force, 首先用一个unordered_map word_count记录L中单词的出现次数，然后用一个循环从S的第一个字符开始到里S末尾距离为L.size()*L[0].length()的字符，匹配L中的单词。在上面的每个循环中，用一个临时unordered_map unused记录当前word剩余出现次数（word_count中单词出现次数减去该word已经出现的次数），如果当前word没有出现在word_count中或者该单词的剩余出现次数为0，说明当前搜索的S子串不是L中单词的组合；否则，将该单词的剩余出现次数减一，判断剩余出现次数是否为0，如果为0，从unused中除去该单词。最后判断unused是否为空，如果为空说明已经找到L中所有单词的一个组合，将最外层循环中的index放到结果中。
class Solution {public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> res; int l = L.size(); if(l == 0) return res; int wl = L[0].length(); if(S.length() < l*wl) return res; unordered_map<string, int> word_count; for(auto w:L) word_count[w]++; for(int i = 0; i <= S.length()-l*wl; i++){ unordered_map<string,int> unused(word_count); for(int j = i; j < i+l*wl ; j += wl){ auto pos = unused.find(S.substr(j,wl)); if(pos == unused.end() || pos->second == 0) break; if(--(pos->second) == 0) unused.erase(pos); } if(unused.empty()) res.push_back(i); } return res; }};
Substring with Concatenation of All Words