Word Pattern

Word Pattern

What is this problem about?

"Word Pattern" asks if a pattern string and a space-separated string s follow the same structure. For example, if the pattern is abba, then s must consist of four words where the first and last words are the same, and the middle two words are the same (but different from the first). It is essentially a problem of finding a Bijective Mapping (one-to-one correspondence) between characters and words.

Why is this asked in interviews?

This "Easy" problem is common at companies like Apple and Amazon. It tests basic Hash Table usage and the ability to handle mapping constraints. A common pitfall is ensuring the mapping is unique in both directions: two different characters shouldn't map to the same word, and vice versa.

Algorithmic pattern used

The pattern is Hash Mapping. You can use two hash maps (or one hash map and one set) to store the pairings:

1. charToWord map.
2. wordToChar map. Iterate through the pattern and the words of s simultaneously. If a mapping already exists but doesn't match the current pair, return false.

Example explanation

Pattern: xyyx, String: dog cat cat dog.

1. x -> dog. Store x: dog and dog: x.
2. y -> cat. Store y: cat and cat: y.
3. y -> cat. Map has y: cat. Match!
4. x -> dog. Map has x: dog. Match! Result: True.

Common mistakes candidates make

• One-way Mapping: Only checking if a character maps to a word, but not if the word maps back to the same character. This fails on pattern="abba", s="dog dog dog dog".
• Length Mismatch: Forgetting to check if the number of characters in the pattern equals the number of words in the string.
• String Splitting: Incorrectly splitting the string or not handling extra spaces.

Interview preparation tip

Always think about "bijectivity" when you see mapping problems. Using two maps is a safe and clear way to ensure that the relationship is strictly one-to-one.