Sharing my 4ms C++ solution


  • 0
    T
    class Solution {
    private:
        bool wordPatternMatchHelper(string& pattern, int iP, string& str, int iS, vector<string>& myMap)
        {
            int nP = pattern.length();
            int nS = str.length();
            if(iP==nP && iS==nS)
            {
                unordered_set<string> mySet;
                for(int k=0; k<26; k++)
                {
                    if(myMap[k]!="#")
                    {
                        if(mySet.count(myMap[k])==0)
                            mySet.insert(myMap[k]);
                        else
                            return false;
                    }
                }
                return true;
            }
            else if(iP==nP || iS==nS)
                return false;
                
            if(myMap[pattern[iP]-'a']=="#")
            {
                for(int i=iS; i<nS; i++)
                {
                    if(nP-iP<=nS-i)
                    {
                        myMap[pattern[iP]-'a'] = str.substr(iS, i-iS+1);
                        if(wordPatternMatchHelper(pattern, iP+1, str, i+1, myMap))
                            return true;
                        myMap[pattern[iP]-'a'] = "#";
                    }
                }
            }
            else if(iS+myMap[pattern[iP]-'a'].length()<=nS && 
                    myMap[pattern[iP]-'a']==str.substr(iS, myMap[pattern[iP]-'a'].length())){
                        if(wordPatternMatchHelper(pattern, iP+1, str, iS+myMap[pattern[iP]-'a'].length(), myMap))
                            return true;
                    }
            
            return false;
        }
        
    public:
        bool wordPatternMatch(string pattern, string str) {
            vector<string> myMap(26, "#");
            return wordPatternMatchHelper(pattern, 0, str, 0, myMap);
        }
    };

Log in to reply
 

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