首页 > 代码库 > 【leetcode】Substring with Concatenation of All Words (hard) ★
【leetcode】Substring with Concatenation of All Words (hard) ★
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的长度为Slen, L的长度为Llen, L中每个单词的长度为Lstrlen
把L中的单词排序
首个字符遍历S中的每一个字符
然后以首字符为起点，获取Llen个Lstrlen长度的单词，把获取的单词排序。
比较两个排序后的单词是否相同。相同则压入答案，不同则遍历下一个起点。
时间复杂度为O（Slen*Llen*log(Llen)）
结果超时了。分析一下原因：
S: "barfoothefoobarman"
L: ["foo", "bar"]
在遍历第一个起始点时，我们获取了 bar foo
在遍历第4个起始点时，我们获取了 foo the. 但这个foo在遍历第一个起始点时已经遍历过了，故我们做了重复的计算。
------------------------------------------------------------------------------------------------------
下面是大神O（Slen*Lstrlen）的答案
用hash表cn记录每个单词出现的次数
对 i = 0 - Lstrlen 遍历
对 j = i - Slen遍历 ;j+= Lstrlen
获取以j为起点的一个单词。
if(不存在这个单词)
起始位置订到下一个单词起始点，数据清0
else if(存在这个单词，并且出现次数小于cn中统计的次数)
获取的单词数增加
else(存在这个单词，但出现次数大于等于cn中统计的次数)
把起始位置重新定位到这个单词第一次出现之后
if(获取单词数==L中单词数)
压入答案
class Solution {public: //超时 vector<int> findSubstring2(string S, vector<string> &L) { vector<int> ans; if(L.empty()) //L是空的 { return ans; } int Llen = L.size(); int Slen = S.size(); int Lstrlen = L[0].size(); if(Slen < Lstrlen) //S没有L中的字符串长 { return ans; } sort(L.begin(), L.end()); for(int i = 0; i < Slen - Llen * Lstrlen; i++)//起始位置循环 { bool isOK = true; vector<string> cur; for(int j = 0; j < Llen; j++) { cur.push_back(S.substr(i + j * Lstrlen, Lstrlen)); } sort(cur.begin(), cur.end()); for(int j = 0; j < Llen; j++) { if(cur[j] != L[j]) { isOK = false; break; } } if(isOK) { ans.push_back(i); i += Llen * Lstrlen - 1; } } return ans; }};//大神可以通过的代码class Solution2 {private:vector<int> res;map<string,int> cntL;map<string,int> cn;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; for(int i = 0; i < e ; i++) { if(cn.count(L[i]) == 0) { cn[L[i]] = 1; k++; } else { cn[L[i]] += 1; k++; } } string tr ,du; int r = 0; int st = 0; for(int j = 0 ; j < t ; j++) { r = 0; st = j; for(int i = j; i < n; i += t) { tr = S.substr(i,t); if( cn.count(tr) == 0 || cn[tr] == 0 ) { cntL.clear(); r = 0; st = i+t; } else if(cntL[tr] < cn[tr]) { cntL[tr] += 1; r++; } else { du = S.substr(st,t); while(du != tr) { cntL[du]--; r--; st += t; du = S.substr(st,t); } st += t; } if(r == k) { res.push_back(st); du = S.substr(st,t); cntL[du]--; r--; st += t; } } cntL.clear(); } sort(res.begin(),res.end()); return res ; }};
【leetcode】Substring with Concatenation of All Words (hard) ★