LeetCode Substring with Concatenation of All Words-白红宇

LeetCode Substring with Concatenation of All Words

阅读量：5018 次

发布时间：2019-06-12

本文共 3237 字，大约阅读时间需要 10 分钟。

class Solution {public:    vector
     
       findSubstring(string S, vector
      
        &L) {        vector
       
         res;		unordered_map
        
          stat;		unordered_map
         
           run;        int len = S.size();		int num = L.size();		int per = 0;		if (num == 0 || !(per = L[0].size())) return res;				int part= num * per;		if (part > len) return res;				int end = len - part;        unordered_map
          
           ::iterator iter; pair
           
            
             ::iterator, bool> ir; for (int i=0; i
             
              (L[i], 1)); if (ir.second == false){ ir.first->second++; } } int i, j, pos, wc; string pre; for (i=0; i<=end; i++) { pos = i; for (j=0; j
              
               second; ir = run.insert(pair
               
                (seg, 1)); iter = ir.first; if (ir.second) { pre = seg; continue; } } iter->second++; if (wc < iter->second) break; } if (j == num) res.push_back(i); run.clear(); } return res; }};

暴力解，跑了500+ms，如果每次都这样把题目应付过去，显然做题没有意义了。于是看Leetcode上关于那题的discuss，有人说可以用解决Minimum Window Substring的方法来解这一题，的确是可以。又搜了份Java实现的代码，一跑竟然也可以达到500ms，看来两种方法效率的确差很多。下面给出自己实现的代码

1 class Solution3 { 2 public: 3     vector
     
       findSubstring(string S, vector
      
        &L) { 4         vector
       
         res; 5         unordered_map
        
          stat; 6         unordered_map
         
           run; 7         int len = S.size(); 8         int num = L.size(); 9         int per = 0;10 11         if (num == 0 || !(per = L[0].size())) return res;12         13         int part = num * per;14         if (part > len) return res;15         16         unordered_map
          
           ::iterator iter;17 pair
           
            
             ::iterator, bool> ir;18 19 for (int i = 0; i < num; i++) {20 ir = stat.insert(pair
             
              (L[i], 0));21 ir.first->second++;22 }23 int wc;24 for (int i = 0; i < per; i++) {25 int step = 0;26 run.clear();27 // scan like a worm, string[spos, epos] is the candidate28 int spos=i, epos = i + per - 1;29 for (; epos < len; epos += per) {30 string seg = S.substr(epos - per + 1, per);31 iter = stat.find(seg);32 // encounter some word not in L33 if (iter == stat.end()) {34 spos = epos + 1;35 step = 0;36 run.clear();37 continue;38 }39 40 wc = iter->second;41 step++;42 43 ir = run.insert(pair
              
               (seg, 0));44 iter = ir.first;45 iter->second++;46 47 // string[spos, epos] is matched48 if (iter->second == wc && step == num) { 49 res.push_back(spos);50 run.find(S.substr(spos, per))->second--;51 step--;52 spos += per;53 continue;54 }55 56 // number of duplicated word exceeds needed57 if (iter->second > wc) { 58 string tmp = S.substr(spos, per);59 // find the first duplicated one60 while(seg != tmp) {61 run.find(tmp)->second--;62 step--;63 spos += per;64 tmp = S.substr(spos, per);65 }66 // then skip it67 iter->second--;68 spos += per;69 step--;70 }71 }72 }73 return res;74 } 75 };

跑了一下在100+ms左右，又习得一策略技能！

参考：

zhuli题解 http://www.cnblogs.com/zhuli19901106/p/3570539.html

java实现 https://github.com/shengmin/coding-problem/blob/master/leetcode/substring-with-concatenation-of-all-words/Solution.java

leetcode资料 http://leetcode.com/2010/11/finding-minimum-window-in-s-which.html

转载于:https://www.cnblogs.com/lailailai/p/3617588.html

你可能感兴趣的文章