Word Pattern II - Solution & Explanation

Problem Overview: You get a pattern string where each character should map to a non-empty substring of another string. The mapping must be bijective: one pattern character maps to exactly one substring, and no two characters can map to the same substring. The task is to determine whether the entire string can be segmented so the pattern expansion exactly recreates it.

Approach 1: Brute Force Backtracking (Exponential Time, O(n^n) time, O(n) space)

The straightforward idea is to try every possible substring assignment for each pattern character. Iterate through the string and assign a candidate substring to the current pattern character. Recursively process the remaining pattern and string. If a mismatch occurs, backtrack and try a different substring. A hash map stores the mapping from pattern character to substring, while a set ensures no two characters map to the same substring. This brute force search explores many invalid combinations, but it establishes the basic recursive structure of the problem.

Approach 2: Backtracking with Hash Map + Pruning (Optimal, Exponential Time, O(n^n) worst-case time, O(n) space)

The practical solution still uses backtracking but prunes invalid paths early. Maintain two structures: a hash map from pattern character to substring and a set (or reverse map) tracking substrings already used. When you encounter a pattern character that already has a mapping, simply check whether the string starting at the current index matches that substring. If it does, continue recursion; otherwise stop immediately. When the character has no mapping yet, iterate over possible substring endpoints, assign the substring if unused, and recurse. After recursion, remove the mapping (classic backtracking). This dramatically reduces the search space because invalid mappings terminate early.

Two-pointer slicing on the string combined with hash lookups keeps each recursive step efficient. The recursion depth is bounded by the pattern length, and the space usage comes primarily from the recursion stack and the mapping structures.

Conceptually this problem combines substring exploration from string processing with constraint enforcement via a hash table. The search itself is a classic backtracking pattern where you try a choice, recurse, and undo the choice if it fails.

Recommended for interviews: The hash map + backtracking approach is the expected solution. Interviewers want to see you enforce the bijection using both a mapping and a used-substring set while pruning mismatches early. Mentioning the brute force idea first shows you understand the search space, but implementing the pruned backtracking demonstrates stronger algorithmic reasoning.