207. Word Pattern II

Try to assign each pattern character a non-empty substring of s. Keep a map char->word and a set of used words to enforce bijection. When a character is already mapped, the next chunk of s must equal its word; otherwise try every prefix as its word and recurse.

Search over substring assignments

Match pattern[pi] against s[si:]. Maintain mapping (char → word) and used (the set of assigned words, to keep the mapping one-to-one).

def backtrack(pi, si):
    if pi == len(pattern) and si == len(s): return True   # both consumed together
    if pi == len(pattern) or si == len(s): return False
    c = pattern[pi]
    if c in mapping:
        w = mapping[c]
        return s.startswith(w, si) and backtrack(pi+1, si+len(w))
    for end in si+1 .. len(s):
        w = s[si:end]
        if w in used: continue                  # bijection: word already taken
        mapping[c] = w; used.add(w)
        if backtrack(pi+1, end): return True
        del mapping[c]; used.remove(w)          # backtrack
    return False

The twin base cases ensure both pattern and s finish at the same time.

Worked example

pattern = "abab", s = "redblueredblue".

• a -> "red", b -> "blue" reproduces red blue red blue = s → true.

For pattern = "aabb", s = "xyzabcxzyabc", no consistent bijection exists → false.

Complexity

• Time: exponential in the worst case (trying every prefix split), bounded by the small input limits.
• Space: O(len(pattern)) for the maps and recursion.

class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        return backtrack(pattern, 0, s, 0, new HashMap<>(), new HashSet<>());
    }

    private boolean backtrack(String pattern, int pi, String s, int si,
                              Map<Character, String> mapping, Set<String> used) {
        if (pi == pattern.length() && si == s.length()) return true;
        if (pi == pattern.length() || si == s.length()) return false;
        char c = pattern.charAt(pi);
        if (mapping.containsKey(c)) {
            String w = mapping.get(c);
            if (s.startsWith(w, si)) {
                return backtrack(pattern, pi + 1, s, si + w.length(), mapping, used);
            }
            return false;
        }
        for (int end = si + 1; end <= s.length(); end++) {
            String w = s.substring(si, end);
            if (used.contains(w)) continue;
            mapping.put(c, w);
            used.add(w);
            if (backtrack(pattern, pi + 1, s, end, mapping, used)) return true;
            mapping.remove(c);
            used.remove(w);
        }
        return false;
    }
}