Substring with Concatenation of All Words

时间：2014-03-11 00:41:21 收藏：0 阅读：485

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).

此题我已欲仙欲死……

首先，关于题意的理解，必须所有字典里的串都出现。

其次，暴力法我的代码有问题，超时……关键是我不知道为什么超时，和别人的代码没差多少啊……

痛苦了1个小时之后，我把网上让其他人的代码贴上去，这次没超时，1700ms……

但是，我认为那个代码是不美的，于是我又优化了一下,1600ms,心里那个爽~~~

看了下discuss，有个更优的算法，贴过去，偶滴神啊，190ms……

不过他的算法貌似没用到我的优化方法，理论上这个算法还有优化空间。优化是针对多次出现的重复字段进行的。

呈上暴力法优化后程序。

class 
Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> re;
        vector<int> stop(S.length(),0);
        map<string,int> m;
        int 
l_size = L.size();
        int 
s_length =S.length();
         
         
        if(L.size() ==0) return 
re;
        int 
size = L[0].length();
        for(int 
i = 0 ;i < L.size();i++)
        {
            m[L[i]]++;
        }
    
        int 
ttt =size*l_size;
        map<string,int> test;
         
        for(int 
i = 0 ; i + ttt <= s_length;i++ )
        {
            if(stop[i] == 1)continue;
            test.clear();
            int 
j;
            for( j = 0 ; j < l_size ;j++)
            {
                string temp = S.substr(i + j*size, size);
                if(m.find(temp) != m.end())
                {
                    test[temp]++;
                    if(m[temp] < test[temp])break;
                     
                }
                else
                {
                    for(int 
k = 1 ; k<=j ;k++)stop[i + k*size] = 1;
                    break;
                     
                }
            }
            if(j == l_size)
            {
                re.push_back(i);
                for(int 
k = 0 ;i + k*size +size<=s_length ;k++)
                {
                    string temp1 = S.substr(i + k*size,size);
                    string temp2 = S.substr(i+ttt +k*size,size);
                    if(temp1 == temp2)
                    {
                        stop[i + k*size +size] = 1;
                        re.push_back(i + k*size +size);
                    }
                    else
                    {
                        stop[i + k*size +size] = 1;
                        break;
                    }
                }
            }
        }
         
        return 
re;
    }
};

　　这题刷的很不爽，还是要笑看人生啊！

这里把比较好的算法贴上来。下次刷的时候把这个算法再优化下。

class 
Solution {
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 ;    
 }
};

　　看了这个算法，洒家这一下午值了！

Substring with Concatenation of All Words,布布扣,bubuko.com

原文：http://www.cnblogs.com/pengyu2003/p/3592529.html