Sharing my C++ solution using hash tables


  • 0
    T
    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            int m = words.size();
            int n = words[0].length();
            int l = s.length();
            
            unordered_map<string, int> myMap;
            unordered_map<string, int>::const_iterator got;
            int i, j;
            for(i=0; i<m; i++)
            {
                got = myMap.find(words[i]);
                if(got==myMap.end())
                    myMap.insert({words[i], 1});
                else
                    myMap[words[i]]++;
            }
            
            vector<int> result;
            int size;
            unordered_map<string, int> myCopy;
            for(i=0; i<=l-m*n; i++)
            {
                myCopy = myMap;
                size = myCopy.size();
                for(j=1; j<=m; j++)
                {
                    got = myCopy.find(s.substr(i+(j-1)*n, n));
                    if(got!=myCopy.end() && got->second>0)
                    {
                        myCopy[s.substr(i+(j-1)*n, n)]--;
                        if(got->second == 0)
                            size--;
                    }
                }
                if(size == 0)
                    result.push_back(i);
            }
            return result;
        }
    };

Log in to reply
 

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