Word Pattern II - Video Solutions

Problem Overview: You get a pattern string and a target string. Each character in the pattern must map to a non-empty substring of the target so that replacing pattern characters with their mapped substrings reconstructs the entire string. The mapping must be bijective: one character maps to exactly one substring and no two characters share the same substring.

Approach 1: Backtracking with Hash Maps (Exponential Time, Optimal for This Problem)

This problem is fundamentally a search problem. You try assigning substrings of the input string to each pattern character and recursively verify whether the rest of the pattern can match the remaining string. Use a hash map to store the mapping from pattern character to substring and a set (or reverse map) to ensure no two characters map to the same substring. At each step, iterate through possible substring splits starting from the current index and attempt a mapping if the character is not yet assigned. If the character already has a mapping, simply check whether the next part of the string matches it.

The recursion explores candidate mappings and backtracks when a mismatch occurs. The key insight is enforcing the bijection constraint while incrementally consuming the string. Time complexity is exponential in the worst case, commonly expressed as O(n * m^n) where n is the pattern length and m is the string length, because multiple substring partitions are explored. Space complexity is O(n) for recursion depth and the mapping structures.

Approach 2: Backtracking with Bidirectional Mapping (Pruning Optimization)

A cleaner implementation maintains two structures: a map from pattern character to substring and another from substring back to pattern character. This removes the need for a separate set and makes bijection checks constant time. During recursion, if a character already has a mapped substring, directly verify the string prefix using substring comparison. Otherwise, iterate over candidate substrings and only assign those not already mapped in the reverse structure.

This approach still uses backtracking, but pruning invalid mappings earlier significantly reduces exploration in practice. The algorithm repeatedly performs substring checks and hash lookups, relying on hash table operations for constant-time mapping validation. Time complexity remains exponential O(n * m^n) in the worst case, with O(n) space for recursion and maps. Since strings are heavily manipulated, understanding string operations is essential.

Recommended for interviews: Interviewers expect the backtracking solution with a hash map and a set (or bidirectional maps). A brute-force mindset shows you understand substring partitioning, but the key signal is enforcing the bijection constraint efficiently while pruning invalid paths early. Writing clean recursive code with careful state rollback demonstrates strong control of recursion and backtracking patterns.