Share my C++ backtracking solution


  • 8
    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.


  • 0
    A

    @yaolinviolin I think we should add "ins=false" at line 36.


Log in to reply
 

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