Word Pattern II

medium backtracking string hash map

Problem

Given a pattern and a string s, return true if s matches the pattern under a bijective mapping pattern_letter ↔ substring.

Inputpattern = "abab", s = "redblueredblue"

Outputtrue

a → "red", b → "blue".

pattern

def word_pattern_match(pattern, s):
    mapping = {}
    used = set()
    def back(p, q):
        if p == len(pattern) and q == len(s):
            return True
        if p == len(pattern) or q == len(s):
            return False
        ch = pattern[p]
        if ch in mapping:
            sub = mapping[ch]
            return s.startswith(sub, q) and back(p + 1, q + len(sub))
        for k in range(q + 1, len(s) + 1):
            sub = s[q:k]
            if sub in used: continue
            mapping[ch] = sub; used.add(sub)
            if back(p + 1, k): return True
            del mapping[ch]; used.remove(sub)
        return False
    return back(0, 0)

function wordPatternMatch(pattern, s) {
  const map = new Map(), used = new Set();
  function back(p, q) {
    if (p === pattern.length && q === s.length) return true;
    if (p === pattern.length || q === s.length) return false;
    const ch = pattern[p];
    if (map.has(ch)) {
      const sub = map.get(ch);
      return s.startsWith(sub, q) && back(p + 1, q + sub.length);
    }
    for (let k = q + 1; k <= s.length; k++) {
      const sub = s.slice(q, k);
      if (used.has(sub)) continue;
      map.set(ch, sub); used.add(sub);
      if (back(p + 1, k)) return true;
      map.delete(ch); used.delete(sub);
    }
    return false;
  }
  return back(0, 0);
}

class Solution {
    Map map = new HashMap<>();
    Set used = new HashSet<>();
    public boolean wordPatternMatch(String pattern, String s) { return back(pattern, 0, s, 0); }
    boolean back(String p, int i, String s, int j) {
        if (i == p.length() && j == s.length()) return true;
        if (i == p.length() || j == s.length()) return false;
        char c = p.charAt(i);
        if (map.containsKey(c)) {
            String sub = map.get(c);
            return s.startsWith(sub, j) && back(p, i + 1, s, j + sub.length());
        }
        for (int k = j + 1; k <= s.length(); k++) {
            String sub = s.substring(j, k);
            if (used.contains(sub)) continue;
            map.put(c, sub); used.add(sub);
            if (back(p, i + 1, s, k)) return true;
            map.remove(c); used.remove(sub);
        }
        return false;
    }
}

class Solution {
    unordered_map mp;
    unordered_set used;
    bool back(const string& p, int i, const string& s, int j) {
        if (i == (int)p.size() && j == (int)s.size()) return true;
        if (i == (int)p.size() || j == (int)s.size()) return false;
        char c = p[i];
        if (mp.count(c)) {
            const string& sub = mp[c];
            return s.compare(j, sub.size(), sub) == 0 && back(p, i + 1, s, j + sub.size());
        }
        for (int k = j + 1; k <= (int)s.size(); k++) {
            string sub = s.substr(j, k - j);
            if (used.count(sub)) continue;
            mp[c] = sub; used.insert(sub);
            if (back(p, i + 1, s, k)) return true;
            mp.erase(c); used.erase(sub);
        }
        return false;
    }
public:
    bool wordPatternMatch(string pattern, string s) { return back(pattern, 0, s, 0); }
};

Explanation

We need to decide if each letter of pattern can stand for a chunk of s so the whole thing lines up — and the mapping must be bijective (different letters map to different chunks). Since we don't know how long each chunk should be, we try every possibility with backtracking.

The recursion back(p, q) tracks a position p in the pattern and a position q in the string. We keep a mapping from letters to substrings and a used set of substrings already claimed, so no two letters grab the same chunk.

If the current pattern letter is already mapped, there's no choice: the string must continue with exactly that substring, so we check s.startswith(sub, q) and move both pointers forward. This prunes the search heavily.

If the letter is new, we try every possible chunk s[q:k] as its value (skipping any chunk already in used), recurse, and on failure undo the mapping before trying a longer chunk. We succeed only when both p and q reach the end together.

Example: pattern = "abab", s = "redblueredblue". Binding a → "red" and b → "blue" makes the second ab reuse those exact chunks, consuming the whole string — so the answer is true.

Time: O(n^m) Space: O(m + n)