首页 > 代码库 > [LeetCode] Substring with Concatenation of All Words(good)
[LeetCode] Substring with Concatenation of All Words(good)
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中直接遍历，而是把S按照L中每个字符串的长度进行分组，妙
class Solution {private: vector<int> res; map<string,int> cntL; map<string,int> cn;//存储L中string及其出现次数 int n ;public: vector<int> findSubstring(string S, vector<string> &L){ res.clear(); cntL.clear(); cn.clear(); n = S.length(); int e = L.size(); int t = L[0].length(); int k = 0;//k表示L中一共有几个string for(int i = 0; i < e ; i++){//在cn中存储L中string及其出现次数 if(cn.count(L[i]) == 0){ cn[L[i]] = 1; k++; }else{ cn[L[i]] += 1; k++; } }//end for string s0 ,s1; int r = 0; int st = 0; for(int j = 0 ; j < t ; j++){//L中每个string的长度是t r = 0; st = j; cntL.clear(); for(int i = j; i < n; i += t){ s0 = S.substr(i,t); if( cn.count(s0) == 0 || cn[s0] == 0 ){ cntL.clear(); r = 0; st = i+t; }else if(cntL[s0] < cn[s0]){ cntL[s0] += 1;//cntL中记录S中出现L中string及次数 r++;//r表示S中遇到的L中string的总共数 r <= k }else{//如果S中子字符串比L中某个多了，则开始下标st必然要越过这个多出来的字符，这个多出来的字符即是s0 s1 = S.substr(st,t); while(s1 != s0){ cntL[s1]--; r--; st += t; s1 = S.substr(st,t); } st += t; } if(r == k){//利用上个记录，以免多用时间 res.push_back(st); s1 = S.substr(st,t); cntL[s1]--; r--; st += t; } }//end for }//end for sort(res.begin(),res.end()); return res ; }//end func};
[LeetCode] Substring with Concatenation of All Words(good)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。