【Substring with Concatenation of All Words】cpp

题目：

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

代码：

class Solution {

public:

    vector<int> findSubstring(string s, vector<string>& words) {

            vector<int> ret;

            if ( words.empty() || s.empty() ) return ret;

            const int len_w = words[].size();  // length of substring in words

            const int end = words.size()*len_w; // total length of words

            if ( end>s.size() ) return ret;     // s size not enough

            map<string, int> ori;

            for ( int i=; i<words.size(); ++i )

            {

                if ( ori.find(words[i])==ori.end() ){

                    ori[words[i]] = ;

                }

                else{

                    ori[words[i]]++;

                }

            }

            map<string, int> found;

            int match_num = ;

            int begin = ;

            int i = ;

            while ( i<s.size() )

            {

                //cout << "i:" << i << endl;

                //cout << "m:" << match_num << endl;

                //cout << "begin:" << begin << endl;

                // match one substring in words

                if ( ori.find(s.substr(i,len_w))!=ori.end() )

                {

                    found[s.substr(i,len_w)]++;

                    // substring occur more than times in words

                    if ( found[s.substr(i,len_w)]>ori[s.substr(i,len_w)] )

                    {

                        found.clear();

                        match_num = ;

                        begin++;

                        i=begin;

                        continue;

                    }

                    i = i+len_w;

                    match_num++;

                    //cout << match_num << endl;

                    // match all substrings in words and push back a starting indices

                    if ( match_num==words.size() )

                    {

                        ret.push_back(i-end);

                        found.clear();

                        begin++;

                        i = begin;

                        match_num=;

                    }

                }

                // not match

                else

                {

                    found.clear();

                    match_num = ;

                    begin++;

                    i=begin;

                }

            }

            return ret;

    }

};

tips：

采用双指针技巧。

维护几个关键变量：

1. begin：可能的有效开始位置

2. match_num: 已经匹配上的words中的个数

3. ori: words中每个string，及其出现的次数

4. found: 当前已匹配的interval中，words中每个string，及其出现的次数

思路就是如果找到了匹配的某个string,i就不断向后跳；跳的过程中可能有两种情况不能跳了：

a) 下一个固定长度的子字符串不匹配了

b) 下一个固定长度的子字符串虽然匹配上了words中的一个，但是匹配的数量已经超过了ori中该string的数量

如果一旦不能跳了，就要把match_num和found归零；而且需要回溯到begin++的位置，开始新一轮的搜寻。

这里有个细节要注意：

直接用found.clear()就可以了，如果一个一个清零，会超时。

======================================

第二次过这道题，代码简洁了，一些细节回忆着也写出来了。保留一个ori用于判断的，再维护一个wordHit用于计数的；ori不能动，wordHit每次clear后默认的value=0。

class Solution {

public:

    vector<int> findSubstring(string s, vector<string>& words) {

            vector<int> ret;

            if ( words.empty() ) return ret;

            int len = words[].size();

            if ( len*words.size()>s.size() ) return ret;

            map<string, int> wordHit;

            map<string ,int> ori;

            for ( int i=; i<words.size(); ++i ) ori[words[i]]++;

            for ( int i=; i<=s.size()-len*words.size(); ++i )

            {

                wordHit.clear();

                int j = i;

                int hitCouts = ;

                while ( hitCouts<words.size() && j<=s.size()-len )

                {

                    // find word and not hit already

                    if ( ori.find(s.substr(j,len))==ori.end() ) break;

                    if ( wordHit[s.substr(j,len)]<ori[s.substr(j,len)] )

                    {

                        wordHit[s.substr(j,len)]++;

                        j += len;

                        hitCouts++;

                    }

                    else { break; }

                }

                // if hits all words

                if ( hitCouts==words.size() ) ret.push_back(i);

            }

            return ret;

    }

};

巴特西

【Substring with Concatenation of All Words】cpp

最新文章

热门文章