C++ AC solution using backtracking with explaination


  • 0
    F

    Using backtracking

    class Solution {
    public:
        bool wordPatternMatch(string pattern, string str) {
            unordered_map<char,string> m;
            unordered_set<string> s;
            int pstart = 0; 
            int sstart = 0;
            return backtracking(pattern,str,m,s,pstart,sstart);
        }
        bool backtracking(string pattern,string str, unordered_map<char,string> &m,unordered_set<string> &s, int pstart,int sstart){
            // pstart : index of pattern
            // sstart : index of str
            if(pstart == pattern.size() && sstart == str.size()) return true;
            if(pstart == pattern.size() || sstart == str.size()) return false;
            if(m.find(pattern[pstart]) == m.end()){
                for(int j = sstart+1; j <= str.size();j++){
                    if(s.find(str.substr(sstart,j-sstart)) != s.end()) {
                        // we can not let two different pattern characters map into the same string
                        continue; 
                    }
                    m[pattern[pstart]] = str.substr(sstart,j-sstart);
                    s.insert(str.substr(sstart,j-sstart));
                    if(backtracking(pattern,str,m,s,pstart+1,j)) return true;
                    // not good, trace back
                    m.erase(pattern[pstart]);
                    s.erase(str.substr(sstart,j-sstart));
                }
                // we tried all possible states, all can not pass
                return false;
            }
            else{
                // check if there is such a string that matches str1 in map  
                auto str1 = m[pattern[pstart]];
                auto n = str1.size();
                for(int i = 0;i<n;i++){
                    if(sstart+i > str.size() || str1[i] != str[sstart+i]){
                        // if one character is not same, return false
                        return false;
                    }
                }
                // it seems good now, let us continue 
                return backtracking(pattern,str,m,s,pstart+1,sstart+n);
            }
        }
    };
    

Log in to reply
 

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