题目

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

分析

这道题真的恶心到我了。一个下午都没写出来。不过后来弄出来之后又觉得异常简单。
思路：由words可知最终组成的子串的长度，枚举子串的开头，依次判断是否符合规则即可。

实现一

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words){
        vector<int> ans;
        int wl=words[0].size(), sl=s.size(), n=words.size();
        unordered_map<string, int> dict;
        for(int i=0; i<n; i++)
            dict[words[i]]++;
        
        unordered_map<string, int> times;
        for(int left=0; left+wl*n<=sl; left++){
            //init
            bool valid = true;
            for(int i=left; i<left+wl*n; i+=wl){
                string str = s.substr(i, wl);
                if(!dict.count(str)){
                    times.clear();
                    valid = false;
                    break;
                }
                times[str]++;
            }
            if(!valid) continue;
            
            //valid?
            for(int i=0; i<n; i++){
                if(times.count(words[i])==0 || dict[words[i]]!=times[words[i]]){
                    valid=false;
                    break;
                }
            }
            if(valid){
                ans.push_back(left);
            }
            
            //next
            times.clear();
        }
        return ans;
    }
};

思考一

提交成功后发现所有选手的运行时间的分布有两个明显的驼峰，而我的方法在后一个驼峰。所以考虑还有更好的算法。原算法的复杂度为O(slwln)思考后发现如果假设s是由与words中字符串长度相等的子串组成的话，会简单很多。那么可以根据words中字符串的长度wl来将答案分为wl类，这样可以将复杂度降为O(sl/wlwln)=O(sl*n)。而在每一组中，以wl为间隔枚举开头，并且在计算下一组的状态时，可以通过“掉前一组的头，加上这一组的尾”来实现。

实现二

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        int wl=words[0].size(), sl=s.size(), n=words.size();
        unordered_map<string, int> dict;
        for(int i=0; i<n; i++)
            dict[words[i]]++;
        
        for(int group=0; group<wl; group++){
            unordered_map<string, int> times;
            for(int count=0, left=group; left+n*wl<=sl; left+=wl){
                for(int i=left+count*wl; count<n && i+wl<=sl; i+=wl){
                    string str = s.substr(i, wl);
                    times[str]++;
                    count++;
                }
                if(count<n)
                    return ans;
                
                bool valid=true; 
                for(int i=0; i<n; i++){
                    if(times.count(words[i])==0 || dict[words[i]]!=times[words[i]]) {
                        valid=false;
                        break;
                    }
                }
                if(valid){
                    ans.push_back(left);
                }
                string str=s.substr(left, wl);
                times[str]--;
                count--;
                
            }
        }
        return ans;
    }
};

思考二

果然改变算法之后进入了第一梯队，开心。