Lintcode 829: Word Pattern II

https://www.lintcode.com/problem/word-pattern-ii/description

Notes:

This question is a very good back-tracking problem.

The key for back-tracking is how to recover (or go back) the previous condition.

In this question, we need to correlate the letter in pattern with the substring in the string. So we need two hash maps to record this bijection relationship.

When we plan to move from one step to the next step, we need to make judgement whether we should go or not.

(1) If we can make a decision right away without further exploring, we should stop immediately; and then move on to the next possible step;

(2) if we cannot tell right now, we have to continue the exploring to the next step (this is called dfs);

(3) before we move on to the next step, we should know exactly what kinds of changes have been made to the key parameters in order to move onto the next step (and this is the key to this question);

(4) if the result from the further exploring is not valid, we need to recover the changes made in step (3) (this is called back-tracking);

(5) if the result from the further exploring is valid, we find a valid solution and can return true;

(6) if we have tried all the possible paths but still cannot find a valid one, return false.


See the code below:

class Solution {
public:
    /**
     * @param pattern: a string,denote pattern string
     * @param str: a string, denote matching string
     * @return: a boolean
     */
    bool wordPatternMatch(string &pattern, string &str) {
        // write your code here
        unordered_map<char, string> m1;
        unordered_map<string, char> m2;
        return dfs(pattern, 0, str, 0, m1, m2);
    }

private:
    bool dfs(string &s1, int id1, string &s2, int id2, unordered_map<char, string> &m1, unordered_map<string, char> &m2) {
        if(id1 == s1.size()) return id2 == s2.size();
        if(id2 == s2.size()) return id1 == s1.size();
        if((int)s1.size() - id1 > (int)s2.size() - id2) return false;
        char c = s1[id1];
        for(int i=id2; i<s2.size(); ++i) {
            string s = s2.substr(id2, i-id2+1);
            if(m1.count(c) && m1[c] != s) continue;
            if(m2.count(s) && m2[s] != c) continue;
            bool f1 = false, f2 = false;
            if(!m1.count(c)) {//f1 used to label the real change in m1;
                m1[c] = s;
                f1 = true;
            }
            if(!m2.count(s)) {//f2 used to label the real change in m2;
                m2[s] = c;
                f2 = true;
            }
            if(dfs(s1, id1+1, s2, i+1, m1, m2)) return true;
            if(f1) m1.erase(c);
            if(f2) m2.erase(s);
        }
        return false;
    }
}