Code Implementation

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        def backtrack(pi, si, p2w, w2p):
            if pi == len(pattern) and si == len(s):
                return True
            if pi == len(pattern) or si == len(s):
                return False
            ch = pattern[pi]
            for end in range(si+1, len(s)+1):
                word = s[si:end]
                if ch in p2w:
                    if p2w[ch] == word:
                        if backtrack(pi+1, end, p2w, w2p):
                            return True
                else:
                    if word in w2p:
                        continue
                    p2w[ch] = word
                    w2p[word] = ch
                    if backtrack(pi+1, end, p2w, w2p):
                        return True
                    del p2w[ch]
                    del w2p[word]
            return False
        return backtrack(0, 0, {}, {})
      

class Solution {
public:
    bool wordPatternMatch(string pattern, string s) {
        unordered_map<char, string> p2w;
        unordered_map<string, char> w2p;
        return backtrack(pattern, s, 0, 0, p2w, w2p);
    }
    bool backtrack(const string& pattern, const string& s, int pi, int si,
                   unordered_map<char, string>& p2w,
                   unordered_map<string, char>& w2p) {
        if (pi == pattern.size() && si == s.size()) return true;
        if (pi == pattern.size() || si == s.size()) return false;
        char ch = pattern[pi];
        for (int end = si + 1; end <= s.size(); ++end) {
            string word = s.substr(si, end - si);
            if (p2w.count(ch)) {
                if (p2w[ch] == word) {
                    if (backtrack(pattern, s, pi + 1, end, p2w, w2p)) return true;
                }
            } else {
                if (w2p.count(word)) continue;
                p2w[ch] = word;
                w2p[word] = ch;
                if (backtrack(pattern, s, pi + 1, end, p2w, w2p)) return true;
                p2w.erase(ch);
                w2p.erase(word);
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        return backtrack(pattern, s, 0, 0, new HashMap<>(), new HashMap<>());
    }
    private boolean backtrack(String pattern, String s, int pi, int si,
                              Map<Character, String> p2w,
                              Map<String, Character> w2p) {
        if (pi == pattern.length() && si == s.length()) return true;
        if (pi == pattern.length() || si == s.length()) return false;
        char ch = pattern.charAt(pi);
        for (int end = si + 1; end <= s.length(); ++end) {
            String word = s.substring(si, end);
            if (p2w.containsKey(ch)) {
                if (p2w.get(ch).equals(word)) {
                    if (backtrack(pattern, s, pi + 1, end, p2w, w2p)) return true;
                }
            } else {
                if (w2p.containsKey(word)) continue;
                p2w.put(ch, word);
                w2p.put(word, ch);
                if (backtrack(pattern, s, pi + 1, end, p2w, w2p)) return true;
                p2w.remove(ch);
                w2p.remove(word);
            }
        }
        return false;
    }
}
      

var wordPatternMatch = function(pattern, s) {
    function backtrack(pi, si, p2w, w2p) {
        if (pi === pattern.length && si === s.length) return true;
        if (pi === pattern.length || si === s.length) return false;
        let ch = pattern[pi];
        for (let end = si + 1; end <= s.length; ++end) {
            let word = s.slice(si, end);
            if (p2w.hasOwnProperty(ch)) {
                if (p2w[ch] === word) {
                    if (backtrack(pi + 1, end, p2w, w2p)) return true;
                }
            } else {
                if (w2p.hasOwnProperty(word)) continue;
                p2w[ch] = word;
                w2p[word] = ch;
                if (backtrack(pi + 1, end, p2w, w2p)) return true;
                delete p2w[ch];
                delete w2p[word];
            }
        }
        return false;
    }
    return backtrack(0, 0, {}, {});
};
      

Problem Description

You are given a pattern string and a s string. Your task is to determine if s matches the pattern where each character in pattern can be mapped to a non-empty substring of s. The mapping must be bijective: each character in pattern maps to a unique substring in s and vice versa (no two pattern characters map to the same substring, and no substring is used by two pattern characters).

• Each character in pattern must map to one or more characters in s, forming a substring.
• Different pattern characters cannot map to the same substring.
• The entire s must be matched by the concatenation of mapped substrings in the order of pattern.
• There is no guarantee that a solution exists; return true if a valid mapping exists, else false.

Thought Process

At first glance, this problem resembles the classic "word pattern" problem, but with a twist: instead of mapping pattern characters to single words (delimited by spaces), we must map them to arbitrary substrings of s (with no delimiters).

The brute-force approach would be to try every possible way to partition s into as many substrings as there are characters in pattern, and check if a bijective mapping can be established. However, this approach is highly inefficient, especially for longer strings.

To optimize, we can use backtracking. For each character in pattern, we try all possible mappings to substrings of s (starting from the current index), while maintaining two mappings:

• A mapping from pattern character to substring
• A mapping from substring to pattern character (to enforce bijection)

Solution Approach

Let's break down our solution step by step:

1. Recursive Backtracking:
   • We define a recursive function that takes the current indices in pattern and s, and the current mappings.
   • If we've reached the end of both pattern and s, we've found a match.
   • If only one has ended, it's not a match.
2. Trying All Substrings:
   • For the current pattern character, iterate over all possible substrings of s starting at the current index (at least length 1).
3. Mapping and Bijection Check:
   • If the pattern character is already mapped, check if the mapped substring matches the current substring. If so, recurse with the next indices.
   • If not mapped, and the substring isn't already mapped to another pattern character, create the mapping in both directions and recurse.
   • After recursion, backtrack (remove the mapping) to try other possibilities.
4. Termination:
   • If any recursive call returns true, propagate the success upwards.
   • If no mapping works, return false.
5. Why Hash Maps?
   • We use hash maps (dictionaries) for O(1) lookup to enforce the bijection between pattern and substrings.

Example Walkthrough

Let's consider pattern = "abab" and s = "redblueredblue".

1. First character: 'a'. Try mapping 'a' to "r", "re", ..., up to "redblue".
   • Suppose we try 'a' = "red".
2. Second character: 'b'. Try mapping 'b' to substrings starting after "red".
   • Try 'b' = "blue".
3. Third character: 'a'. It must match "red" again (since 'a' is already mapped to "red"). The next substring of s is "red".
4. Fourth character: 'b'. Must be "blue" again. The next substring is "blue".
5. Both pattern and s are fully matched. The function returns true.

If at any point a mapping fails (e.g., a pattern character is mapped to a substring that doesn't match the current part of s), we backtrack and try a different mapping.

Time and Space Complexity

• Brute-force: The number of ways to partition s into len(pattern) parts is exponential, as each pattern character can map to substrings of varying lengths. This leads to a complexity of O(k^n), where k is the length of s and n is the length of pattern.
• Optimized (Backtracking): Still exponential in the worst case, but pruning via bijection checks and mapping consistency can significantly reduce the search space in practice.
• Space Complexity: O(n + m), where n is the length of pattern and m is the length of s, due to recursion stack and the size of the mappings.

Summary

The problem requires mapping pattern characters to unique, non-empty substrings of a target string, enforcing a bijection. By using recursive backtracking and hash maps for efficient mapping checks, we can systematically try all possibilities while pruning invalid paths early. This approach is elegant because it directly models the problem's constraints and leverages recursion to explore the solution space efficiently.