Clean and easy to understand C++ backtracking solution


  • 0

    I am using two maps:

    m: key is a single char in pattern, and value is a string to be found in given str

    rm: reversed map. key is a string in given str, and value is a single char in pattern.

    The reason for doing this is because we need to make sure that the matching is 1-to-1 match. We need to make sure one char only has one match, and no more than two strings match the same char. We try to find all possible match relationships, and maintain both maps dynamically.

    class Solution { 
    public:
        bool wordPatternMatch(string pattern, string str) {
            unordered_map<char, string> m;
            unordered_map<string, char> rm;
            
            return dfs(pattern, 0, str, 0, m, rm);
        }
        
        bool dfs(string pattern, int pp, string str, int ps, unordered_map<char, string> &m, unordered_map<string, char> &rm)
        {
            if(pp == pattern.size()) return ps == str.size();
            
            if(m.find(pattern[pp]) != m.end()){
                string match = m[pattern[pp]];
                if(str.substr(ps, min(match.size(), str.size() - ps)) == match){
                    return dfs(pattern, pp + 1, str, ps + match.size(), m, rm);
                }else return false;
            }else{
                for(int j = ps; j < str.size(); j++){
                    string match = str.substr(ps, j - ps + 1);
                    if(rm.find(match) != rm.end()) continue; // already been matched by other char
                    m[pattern[pp]] = match;
                    rm[match] = pattern[pp];
                    if(dfs(pattern, pp + 1, str, ps + match.size(), m, rm)) 
                        return true;
                    // backtracking 
                    m.erase(pattern[pp]);
                    rm.erase(match);
                }
            }
            
            return false;
        }
    };

Log in to reply
 

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