291. Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

Notes: You may assume both pattern and str contains only lowercase letters.

// Backtracking Method
bool helper(const string& pattern, int i, const string& str, int j, unordered_map<char, string>& mp) {
    if (i == pattern.size() && j == str.size()) return true;
    if (i == pattern.size() || j == str.size()) return false;
    char ch = pattern[i];
    for (int k = j; k < str.size(); ++k) {
        string t = str.substr(j, k - j + 1);
        if (mp.count(ch) && mp[ch] == t) {
            if (helper(pattern, i + 1, str, k + 1, mp)) return true;
        } else if (!mp.count(ch)) {
            bool b = false;
            for (auto a : mp) {
                if (a.second == t) {
                    b = true;
                    break;
                }
            } 
            if (!b) {
                mp[ch] = t;
                if (helper(pattern, i + 1, str, k + 1, mp)) return true;
                mp.erase(ch);
            }
        }
    }
    return false;
}
bool wordPatternMatch(string pattern, string str) {
    unordered_map<char, string> mp;
    return helper(pattern, 0, str, 0, mp);
}

// Backtracking Method
bool helper(const string& pattern, int i, const string& str, int j, unordered_map<char, string>& mp, unordered_set<string>& st) {
    if (i == pattern.size() && j == str.size()) return true;
    if (i == pattern.size() || j == str.size()) return false;
    char ch = pattern[i];
    for (int k = j; k < str.size(); ++k) {
        string t = str.substr(j, k - j + 1);
        if (mp.count(ch) && mp[ch] == t) {
            if (helper(pattern, i + 1, str, k + 1, mp, st)) return true;
        } else if (!mp.count(ch)) {
            // skip those substrings already mapped
            if (st.count(t)) continue;
            mp[ch] = t;
            st.insert(t);
            if (helper(pattern, i + 1, str, k + 1, mp, st)) return true;
            mp.erase(ch);
            st.erase(t);
        }
    }
    return false;
}
bool wordPatternMatch(string pattern, string str) {
    unordered_map<char, string> mp;
    unordered_set<string> st;
    return helper(pattern, 0, str, 0, mp, st);
}