【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 ;    
 }
};