Word Pattern II

Word Pattern II

What is this problem about?

"Word Pattern II" is the "Medium" version of the previous problem. Here, the string s is not space-separated. You must determine if there exists a way to split s into non-empty substrings such that they follow the pattern.

Why is this asked in interviews?

This is a classic Backtracking problem. Companies like Oracle and Uber ask this to see if you can explore a search space where the boundaries of the "words" are unknown. It requires trying all possible substring lengths for each character in the pattern and backtracking if a choice leads to a dead end.

Algorithmic pattern used

The pattern is Backtracking with a Hash Map.

1. Take the first character of the pattern.
2. If it's already mapped, check if the string starts with that mapped word. If yes, recurse.
3. If it's NOT mapped, try every possible prefix of the remaining string as a potential word.
4. For each prefix, map the character to it, add it to a "used words" set, and recurse.
5. If recursion returns false, undo the mapping (backtrack) and try a longer prefix.

Example explanation

Pattern: aba, String: redblue? No, redbluered.

1. a can be r. Then b must be edblue. Then a must be r. redbluer != redbluered.
2. a can be re. Then b must be dblu. Then a must be re. No.
3. a can be red. Then b must be blue. Then a must be red. red + blue + red = redbluered. Match found!

Common mistakes candidates make

• Missing the "Used Words" set: Allowing two different characters to map to the same substring.
• Infinite Recursion: Not properly advancing the index in the string and pattern.
• Inefficient Substring creation: Repeatedly slicing large strings instead of using indices.

Interview preparation tip

Backtracking is about "Make a choice, recurse, undo the choice." For this problem, the choice is the length of the substring mapped to the current pattern character.