首页 > 代码库 > [Leetcode] Substring with concatenation of all words 串联所有单词的子串
[Leetcode] 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,几个长度相同的单词,让我们找到串联单词的所有起始位置,单词串中,单词串联的顺序不管,且之间都没有空格每个单词串只出现一次。
与题目解答无关:我是把题目做完一遍以后,再在博客上进行整理的,结果发现这道题一下子没有想出来,看以前的做过的答案,才把思路理清楚的,但是很尴尬的是,不知道以前是不是我自己做出来的,很大可能上不是,这道题的参考网站也恰好没有留下记录,所以要是大伙知道这题的原出处,跟我说一声,我标明引用哈。
思路:这道题用到两个哈希表,第一个哈希表先把所有的单词放进去。然后从头开始遍历目标串S(跳出循环的条件是,当S中剩下的字符个数小于L中单词总的长度时),针对每个字符 i,都以其为起始点在目标串S中取长度为m(单个单词的长度),循环的总长度是n*m(L中单词的总长度)放入第二个哈希表中,然后看S中的这个长度为m的单词是否在单词串L存在,若存在,还要继续考虑相同单词是否仅出现一次,如果多了,也跳出循环。代码如下:
1 class Solution { 2 public: 3 vector<int> findSubstring(string S, vector<string> &L) 4 { 5 vector<int> res; 6 if(S.empty() || L.empty()) return res; 7 8 unordered_map<string,int> m1; 9 for(auto &a:L) 10 m1[a]++; 11 12 int n=L.size(),m=L[0].size(),len=S.size(); 13 14 for(int i=0,j;i<=len-n*m;++i) 15 { 16 unordered_map<string,int> m2; 17 18 for(j=i;j<i+n*m;j+=m) 19 { 20 string tem=S.substr(j,m); 21 m2[tem]++; 22 if( !m1.count(tem) || m2[tem] > m1[tem]) 23 break; 24 } 25 if(j>=i+m*n) 26 res.push_back(i); 27 } 28 return res; 29 } 30 };
关于网上的令一种时间复杂度为O(n)的解答,我后续给出自己的理解。这里给出参考地址。
[Leetcode] Substring with concatenation of all words 串联所有单词的子串