首页 > 代码库 > [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 串联所有单词的子串