291. Word Pattern II

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

检查str的substr是否能和pattern中字符一一映射。brute-force DFS遍历所有的substr和mapping的可能，对每个substr检查是否等于已有的mapping，因为是一一映射，包括正向（pattern->str）和逆向检查（str->pattern）。

class Solution {
public:
    /**
     * @param pattern: a string,denote pattern string
     * @param str: a string, denote matching string
     * @return: a boolean
     */
    bool dfs(string &pattern, string &str, unordered_map<char, string> &m, int x, int pos) {
        const int M = str.length(), N = pattern.length();
        if (pos == M) {
            if (x == N) return true;
            return false;
        }
        if (x == N) return false;
        const auto p = pattern[x];
        for (int i = pos; i < M; ++i) {
            const auto sub = str.substr(pos, i - pos + 1);
            if (m.count(p)) {
                if (m[p] != sub) continue;
                if (dfs(pattern, str, m, x + 1, i + 1)) return true;
            } else {
                bool found = false;
                for (const auto &pair : m) {
                    if (pair.second == sub && pair.first != p) {
                        found = true;
                        break;
                    }
                }
                if (found) continue;
                m[p] = sub;
                if (dfs(pattern, str, m, x + 1, i + 1)) return true;
                m.erase(p);
            }
        }
        return false;
    }
    
    bool wordPatternMatch(string &pattern, string &str) {
        unordered_map<char, string> m;
        return dfs(pattern, str, m, 0, 0);
    }
};