请教一题Substring with Concatenation of All Words

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

这个是discuss里面一个人写的算法，看不太懂中间那个if... else if... else... 有没有同学可以解释一下？ 谢谢！

//use hash table to store the list of words L
//for each m char in the string, check if it is a valid word

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> result;
        map<string, int> cntL;
        map<string, int> cn;
        int n = S.length();
        int wordlen = L[0].length();
        int listsize = L.size();
        int count = 0;    // number of words in the list
        //store the list of words in hash table
        for(int i=0; i<listsize; i++)
        {
            //if this key has not been occupied
            if(cn.count(L) == 0)
            {
                cn[L] = 1;
                count++;
            }
            else
            {
                cn[L] += 1;
                count++;
            }
        }

        string tr, du;
        int r = 0;
        int st = 0;

        for(int j=0; j<wordlen; j++)   //for each char in a word
        { r = 0; st = j;
          for(int i=j; i<n; i += wordlen)  //check the string for every word length substring
          {
              tr = S.substr(i, wordlen);  //copy the next m char in the string
              if(cn.count(tr) == 0 || cn[tr] == 0)  //?? if this is not a valid word
              {
                  cntL.clear();
                  r = 0;
                  st = i+wordlen;
              }
              else if(cntL[tr] < cn[tr]) // ???
              {
                  cntL[tr] += 1;
                  r++;
              }
              else
              {
                  du = S.substr(st, wordlen);
                  while(du != tr)
                  {
                      cntL[du]--;
                      r--;
                      st += wordlen;
                      du = S.substr(st, wordlen);
                  }
                  st += wordlen;
              }
              if(r == count)   //if r == count meaning all the words have appeared
              {
                  result.push_back(st);
                  du = S.substr(st, wordlen);
                  cntL[du]--;
                  r--;
                  st += wordlen;
              }
          }
          cntL.clear();
        }
        sort(result.begin(), result.end());
        return result;
    }
};

做过这题的同学来说一下思路也行啊

做过这题的同学来说一下思路吧

这题基本就是暴力解吧
用L里面的词建一个字典 c++就是map 记录每个出现的词以及出现几次 然后遍历字符串所有可能的起点 每个起点扫一遍 一旦发现不在字典中的词或者出现频率超过字典里的值 就退出进行下一个循环即可

这题我做的方法和以上不太一样.
我把L排序, 然后在一个loop中用L的长度扫S. 每次用boyer moore看L里的字串是不是substring, 不过复杂度好高..O(outer loop) * O(n+m) bm

不太明白题意，有人能解释下不？

wizard19900509 发表于 2014-6-28 00:17
这题基本就是暴力解吧
用L里面的词建一个字典 c++就是map 记录每个出现的词以及出现几次 然后遍历字符串所 ...

暴力解现在超时了