Share my 32ms C++ DFS solution


  • 7
    E
    class Solution {
    public:
    bool wordPatternMatch(string pattern, string str) {
        return dfs(pattern,0,str,0);
    }    
    bool dfs(string &pattern, int pp, string &str, int ps){
        if(pp==pattern.length()&&ps==str.length())
            return true;
        if((pattern.length()-pp>str.length()-ps)||pp==pattern.length())
            return false;
        if(pat2str.find(pattern[pp])==pat2str.end()){
            for(int i=1;ps+i<=str.length();i++){
                string tempstr=str.substr(ps,i);
                if(str2pat.find(tempstr)!=str2pat.end())
                    continue;
                pat2str[pattern[pp]]=str.substr(ps,i);
                str2pat[tempstr]=pattern[pp];
                if(dfs(pattern,pp+1,str,ps+i))
                    return true;
                str2pat.erase(tempstr);
            }
            pat2str.erase(pattern[pp]);
            return false;
        }
        else{
            string temp=pat2str[pattern[pp]];
            if(temp==str.substr(ps,temp.length()))
                return dfs(pattern,pp+1,str,ps+temp.length());
            else
                return false;
        }
    }
    private:
    unordered_map<char,string> pat2str;
    unordered_map<string,char> str2pat;
    };

  • 3
    S

    it seems to me that str2pat doesn't have to be a map, unordered_set would do as well


  • 0
    Y

    clean and efficient code! The first two if conditions in dfs greatly reduce time


  • 0

    The condition:

    pattern.length()-pp>str.length()-ps
    

    reduce my code run time from 122ms to 13ms, great!


Log in to reply
 

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