0291. 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.

Analysis

Different from 290, this question requires us to try all the words in the string, and there is no better solution other than brute force search.

Code (copied from Grandyang)

class Solution {
public:
    bool wordPatternMatch(string pattern, string str) {
        unordered_map<char, string> m; // pattern to string
        return helper(pattern, 0, str, 0, m);
    }
    bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m) {
        if (p == pattern.size() && r == str.size()) return true;
        if (p == pattern.size() || r == str.size()) return false;
        char c = pattern[p];
        for (int i = r; i < str.size(); ++i) {
            string t = str.substr(r, i - r + 1);
            // case 1: already have a matching and match correctly
            if (m.count(c) && m[c] == t) {
                if (helper(pattern, p + 1, str, i + 1, m)) return true;
            // case 2: no matching yet, so start matching
            } else if (!m.count(c)) {
                bool b = false;
                // check if current str has other pattern matching
                for (auto it : m) {
                    if (it.second == t) b = true;
                } 
                // if not, create new matching
                if (!b) {
                    m[c] = t;
                    if (helper(pattern, p + 1, str, i + 1, m)) return true;
                    m.erase(c);
                }
            }
        }
        return false;
    }
};

---

Last update: April 1, 2022