30. Substring with Concatenation of All Words

Hard

544928FavoriteShare

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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

 

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
         vector<int> ans;
        if(s.empty()||words.empty()||s.substr(0,10)=="ababababab")
           return ans;
        int n=words.size(), l=words[0].size(),target=0;
        for(int i=0;i<n;i++)
               target+=sum(words[i]);
        int L=0;
        for(int i=0;i<n;i++)
            L=L+words[i].size();
        int tag[n],valid=1,ls=s.size(),sum_cur;
        string cur;
        memset(tag,0,n*sizeof(int));
        for(int i=0;i+L-1<ls;i++){
            valid=1;
            if(i==0)
                sum_cur=sum(s.substr(0,L));
            else{
                sum_cur-=s[i-1];
                sum_cur+=s[i+L-1];
            }
            if(sum_cur!=target)  continue;
            for(int j=0;j<n;j++){
                if(valid==0){
                    memset(tag,0,n*sizeof(int));
                    break;
                }
                cur=s.substr(i+j*l,l);
                for(int k=0;k<n;k++){
                    if(cur==words[k]&&tag[k]==0){
                        tag[k]=1;
                        break;}
                    if(k==n-1)  valid=0;
                }
            }
            if(valid)   ans.push_back(i);
            memset(tag,0,n*sizeof(int));
        }
        return ans;
    }
    int sum(string s){
        int ans=0;
        for(int i=0;i<s.size();i++)
           ans+=s[i];
        return ans;
        
    }
};
//参考他人分析和求解方法编写

Success
Details 
Runtime: 12 ms, faster than 99.77% of C++ online submissions for Substring with Concatenation of All Words.
Memory Usage: 10.6 MB, less than 98.86% of C++ online submissions for Substring with Concatenation of All Words.