Simplest yet efficient enough C++ solution with critical comments


  • 0
    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) 
        {
            map<string, int> word_count, check_count;
            int sLen = s.length(), dictSize = words.size(), wLen = words[0].size(), i = 0, j = 0;
            vector<int> v;
            string word;
            for(; i < dictSize; ++i) word_count[words[i]]++; //set up a count baseline for checking;
            for(i = 0; i < sLen-dictSize*wLen+1; ++i)
            {
                check_count.clear(); //restart;
                for(j = 0; j < dictSize; ++j) //start from position i and check the following sequence;
                {
                    word = s.substr(i+j*wLen, wLen);
                    if(word_count.count(word)) { if(check_count[word]++ == word_count[word]) break;  }
                    else break;
                }
                if(j == dictSize) v.push_back(i); //all words are covered exactly;
            }
            return v;
        }
    };
    

    Using unordered_map might be faster than map here considering the hash map (unordered_map ) is quicker in indexing (constant time) than the binary tree searching in map (logarithmic).


  • 0
    V

    The unordered_map is actually slower in terms of worst case time complexity O(n), although the asymptotic time complexity is O(1).


  • 0
    V

    Correction to the above:- I meant average, not asymptotic


  • 0

    @vshreyas Asymptotic, what do you mean here exactly? After my re-checking, actually the time cost average in both cases, it should be almost the same.


Log in to reply
 

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