Share my C++ backtracking solution


  • 7
    L
    class Solution {
    public:
        unordered_map<char, string> pDict;
        unordered_map<string, char> sDict;
        bool wordPatternMatch(string pattern, string str) {
            return match(pattern, 0, str, 0);
        }
        
        bool match(string &pattern, int i, string &str, int j) {
            int m = pattern.size();
            int n = str.size();
            if (i == m || j == n) {
                if (i == m && j == n)
                    return true;
                return false;
            }
            bool ins = false;
            for (int k = j; k < n; k++) {
                string s = str.substr(j, k - j + 1);
                if (pDict.find(pattern[i]) != pDict.end()) {
                    if (pDict[pattern[i]] != s)
                        continue;
                } else if (sDict.find(s) != sDict.end()) {
                    if (sDict[s] != pattern[i])
                        continue;
                } else {
                    pDict[pattern[i]] = s;
                    sDict[s] = pattern[i];
                    ins = true;
                }
                if (match(pattern, i + 1, str, k + 1))
                    return true;
                if (ins) {
                    pDict.erase(pattern[i]);
                    sDict.erase(s);
                }
            }
            return false;
        }
    };
    

    C++ backtracking. ins indicates whether current round has inserted new mapping pair.
    edited with two maps to ensure on-to-one mapping.
    .


  • 0
    I

    In your solution similar characters can be matched to the same substring. It's not a bijection. For example, wordPatternMatch("ab", "aa") will return true. But it should return false.


  • 0
    L

    You are right. I've edited it.
    Thanks for your comment.


  • 0

    Hi, lightmark. Just a little remind, you seem to have forgotten to remove the following line :-)

    unordered_map<char, string> dict;

  • 0
    L

    Oops. thanks.


  • 0
    J

    The ins is only set once, and never set back to false. You may want to move "bool ins = false;" inside your for-loop. But I am wordering, how could this pass the judge.


  • 0
    Y

    I have the same concern. I think ins should be inside the for-loop. And the test cases are not enough to find out the problem.


Log in to reply
 

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