C++ O(KN) Solution with explanation, 36ms


  • 1
    K

    **1. loop over the offset (i) from 0 to the length of each word(k);

    1. search for each offset starting from i. From the start point (start) and current point (j) is the concatenation. The counts of each word are handled by an unordered_map (word_used). The time complexity of the searching for each offset is O(N); In each check,

      (a) If the concatenation breaks down, jump to the next word and start over;

      (b) If the concatenation has more than the desired number of words, only take out the first word from the concatenation and check again, until the concatenation has less than the desired number of words;
    2. Total time complexity is O(kN).**
    class Solution {
    private:
    unordered_map<string,int> word_used,table;
    inline bool Areallwordsused(){
        for (auto & i:word_used)
            if (i.second!=0) return false;
        return true;
    };
    public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if (words.empty()||s.empty()) return result;
        if (words[0].empty()) return result;
        for (auto & word:words)
            table[word]++;
        word_used=table;
        int len=words[0].size(),n=words.size(),l=s.size();
        for (int i=0;i<len;i++) {
            int start=i,j=start;
            while (start<=l-len*n) {
                unordered_map<string,int>::iterator it=word_used.find(s.substr(j,len));
                if (it!=word_used.end()) {
                    if (it->second>0) {
                        it->second--;
                        j+=len;
                        continue;
                    }
                    else {
                        if (Areallwordsused()) result.push_back(start);
                        word_used[s.substr(start,len)]++;
                        start+=len;
                    }
                }
                else {
                    if (j==start) {
                        start+=len;
                        j=start;
                        continue;
                    }
                    if (Areallwordsused()) result.push_back(start);
                    word_used=table;
                    j+=len;
                    start=j;
                }
            }
            word_used=table;
        }
        return result;
        }
    };
    

  • 0
    the result for testcase
    "anything"
    [""]
    is not the same with expected results.

  • 0
    K

    The question does not define this special/trivial case and does not include this case in the pool.


  • 0

    when searching an empty string, by default, any location is a valid solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.