LeetCode题目:Substring with Concatenation of All Words

By | 2012 年 10 月 28 日

一开始就想复杂了。
设总共有单词N个的话,

一开始的想法是,维护一个有N个int的数组pos,每个值记录了对应word在S中的开头字符的index。
随着在S中向右扫描,每扫到一个在单词集合中的字符,就标记一下pos。如果pos中该字符还没有出现过,那么就标记上当前的S扫描的位置;如果已经出现过了,就将pos在此之前的所有单词记录都清空,然后将当前位置记入pos。每次操作都检测pos数组,看是否所有的字符都已经在S中找到对应了。那么扫描完一遍S,就得到了所有的组合。

但是,有一个问题没有解决,那就是如果S = “mississippi”, L = {“si”,”is”)的时候。当S扫描到index = 3的时候,能找到一个组合S[1,4] = “issi”;但是下一步就出现分支了,是从S[3] = s开始呢,还是从S[4] = i开始呢。

于是就悲剧了。。这个框架其实是不适合于这种有分支的扫描的。

然后又想dp,当L.size()==1的时候;当L.size()==2的时候容易解决;但是当L.size()==3的时候呢,那就是说可以从L.size()==2的结果中,尝试前后能否拼上L[2]来计算一部分结果,另一部分结果是将L[2]插在L[0]和L[1]中间形成的结果中,这其实还好,能想出来解决办法。但是当L.size() > 3的时候呢,那就爆炸了(包括存储空间的爆炸)。

一旦陷入死胡同,想转弯挺难····

然后百度之,发现一个思路其实挺直观的:
一个长度为M*N的子串在S上从左到右平移,每个位置上,直接去判断是不是每一个L中的单词都出现了一次。



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



代码,转自 http://blog.csdn.net/maqingli87/article/details/8009972

class Solution {  
public:  
    vector findSubstring(string S, vector &L) {  
        map words;  
        map curStr;  
        for(int i = 0; i < L.size(); ++i)  
            ++words[L.at(i)];  
        int N = L.size();  
        vector ret;  
        if(N <= 0)   return ret;  
        int M = L.at(0).size();  
        for(int i = 0; i <= (int)S.size()-N*M; ++i)  
        {  
            curStr.clear();  
            int j = 0;  
            for(j = 0; j < N; ++j)  
            {  
                string w = S.substr(i+j*M, M);  
                if(words.find(w) == words.end())  
                    break;  
                ++curStr[w];  
                if(curStr[w] > words[w])  
                    break;  
            }  
            if(j == N)  ret.push_back(i);  
        }  
        return ret;  
    }  
};



错误代码,思路错了。

class Solution {
public:
    vector findSubstring(string S, vector &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector result;
        if(L.size() == 0) return result;
        const int wsize = L[0].size();
        if(wsize == 0) return result;
        //const int minSize = wsize * L.size();
        const int notfound = -1;
        vector pos(L.size(),notfound);
        int si = 0;
        while(S.size() - si >= wsize) {
            vector mwis;
            string possibleword = S.substr(si,wsize);
            for(int wi = 0 ; wi < L.size(); ++wi) {
                if(possibleword == L[wi]) {
                    mwis.push_back(wi);
                }
            }
            int matchwordi = notfound;
            if(mwis.size() > 0) {
                matchwordi = mwis[0];
                for(int i = 1 ;pos[matchwordi] != notfound &&  i < mwis.size(); ++i) {
                    if(pos[mwis[i]] < pos[matchwordi]) {
                        matchwordi = mwis[i];
                    }
                }
            }
            if(matchwordi == notfound) {
                //no match word found, clear all the pos
                for(int i = 0 ; i < pos.size(); ++i) {
                    pos[i] = notfound;
                }
                ++si;
            } else {
                //found one
                if(pos[matchwordi] != notfound) {
                    //if this word is already matched,
                    // clear all the word found before it's old position
                    int prepos = pos[matchwordi];
                    for(int i = 0; i < pos.size(); ++i) {
                        if(pos[i] <= prepos) {
                            pos[i] = notfound;
                        }
                    }
                }
                pos[matchwordi] = si;
                
                //check if all the word is found
                {
                    int minindex = S.size();
                    for(int i = 0 ; minindex != notfound && i < pos.size(); ++i) {
                        if(pos[i] < minindex)
                            minindex = pos[i];
                    }
                    if(minindex != notfound) {
                        //found valid match for all words
                        result.push_back(minindex);
                    }
                }
                
                si += wsize;
            }
        }
        return result;
    }
};

12 thoughts on “LeetCode题目:Substring with Concatenation of All Words

  1. Pingback: [LeetCode] Substring with Concatenation of All Words 串联所有单词的子串 – 数据结构与算法

  2. woodpig

    “一个长度为M*N的子串在S上从左到右平移,每个位置上,直接去判断是不是每一个L中的单词都出现了一次。”这是一个必要条件,但不是充分条件阿。比如S中几个字母和L中一个string顺序不同

    Reply
  3. cong

    偶然看到你的blog,内容很丰富,受益匪浅,不过这篇文章中介绍的方法太慢了. 我想了一种方法,假设word的长度是k,可以将S切成以k为单位长度的段, 例如”barfoothefoobarman”, [“foo”,”bar”], 第一次从第0个开始bar foo the foo bar man, 第二次从第1个字符开始arf oot hef oob arm, 第三次rfo oth efo oba rma, 这样只需要k次循环. 我试过了,只需152ms, 比文章中每个字符挨个循环的方法快了10x. 时间复杂度就省去了,很容易算. 欢迎交流,呵呵

    Reply
    1. uniEagle Post author

      额~~现在这个代码是按照你算法中的切割成长度为k的子串进行匹配的啊,你的算法快在哪儿呢?

      Reply
    2. li

      我不是很理解你的算法为什么会快这么多。 我理解的你的算法是假设word的长度是k, i是当前搜索的位置, 最外层的loop是从0 -》k – 1, 每一层搜索的位置是
      0: 0, k, 2k, 3k …
      1: 1, k+1, 2k+1, 3k+1…
      2: 2, k+2, 2k+2, …

      在我看来这样和所有的位置都搜索是一样的…
      请问能具体说明一下或者介意分享一下code吗?

      Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注