30. Substring With Concatenation of All Words 串联所有单词的子串

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:

s: "barfoothefoobarman"

words: ["foo", "bar"]

You should return the indices: [0,9].

(order does not matter).

Difficulty: Hard

这道题让我们求串联所有单词的子串.所有单词来自输入的数组.所有单词的长度一样,串联的顺序不一定.如题中的例子,可以串联成foobar, barfoo. 这里我们用两个哈希表,一个用来存输入单词数组的每个单词和其的出现次数.然后遍历输入的字符串.设单词的个数为n,每个单词长度为m.每次遍历检查母字符串从该位置开始,每m截取一下查看在第一个哈希表是否存在.如果存在,存入第二个哈希表.如果n个次截取都匹配则这次遍历是符合要求的,存一下结果.

解法1

就是上面分析

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>res;
        if (s.empty()||words.empty()) return res;
        int n = (int)words.size(),m=(int)words[0].size();
        unordered_map<string,int> m1;
        for (auto &a:words) ++m1[a];
        for (int i=0;i<=(int)s.size()-n*m;i++)
        {
            unordered_map<string,int> m2;
            int j = 0;
            for (j=0;j<n;j++)
            {
                string t = s.substr(i+j*m,m);
                if (m1.find(t)==m1.end()) break;
                ++m2[t];
                if (m2[t]>m1[t]) break;
            }
            if (j==n) res.push_back(i);
        }
        return res;
    }
};

解法2

这个解法复杂度为O(n),比较巧妙.这种解法不是一个字符一个字符的遍历,是一个词一个词的遍历.如题中的例子字符的长度n为18.words数组中的有两个单词(cnt=2),每个单词的长度len为3.遍历顺序为0, 3, 6, 8, 12, 15,然后向后移动一个字符1, 4, 7, 9, 13, 16.下次为2, 5, 8, 10, 14, 17.配合代码看看.

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>res;
        if (s.empty()||words.empty()) return res;
        int n = (int)s.size(),cnt=(int)words.size(),len=(int)words[0].size();
        unordered_map<string,int> m1;
        for (string s:words) m1[s]++;
        for (int i=0;i<len;i++)
        {
            int left = i,count=0;
            unordered_map<string,int> m2;
            for (int j=i;j<=n-len;j+=len)
            {
                string t = s.substr(j,len);
                if (m1.count(t))
                {
                    m2[t]++;
                    if (m2[t]<=m1[t])
                        count++;
                    else
                    {
                        //从左到右舍弃,直到m2[t]<=m1[t]
                        while (m2[t]>m1[t])
                        {
                            string t1 = s.substr(left,len);
                            --m2[t1];
                            if (m2[t1]<m1[t1]) --count;
                            left += len;
                        }
                    }
                    if (count==cnt)
                    {
                        res.push_back(left);
                        --m2[s.substr(left,len)];
                        --count;
                        left += len;
                    }
                }
                else //在某次m1[t]不存在,说明此处j与之前的子串不匹配,舍弃,从下个j+len继续
                {
                    m2.clear();
                    count = 0;
                    left=j+len;
                }
            }
        }
        return res;
    }
};

参考 http://www.cnblogs.com/grandyang/p/4521224.html

 
comments powered by Disqus