Coding Interview PatternsWord Pattern
EasyHash Maps

Word Pattern

Explanation & Solution

Practice Problem

Description

Given a pattern and a string s, find if s follows the same pattern.

Here follows means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:

  • Each letter in pattern maps to exactly one unique word in s.
  • Each unique word in s maps to exactly one letter in pattern.
  • No two letters map to the same word, and no two words map to the same letter.

Input: pattern = "abba", s = "dog cat cat dog"

Output: true

Explanation: The bijection is: 'a' -> "dog", 'b' -> "cat".

Constraints

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters
  • 1 <= s.length <= 3000
  • s contains only lower-case English letters and spaces ' '
  • s does not contain any leading or trailing spaces
  • All the words in s are separated by a single space

Approach

Hash Maps pattern

1. Split the String Into Words

  • Split s by spaces to get an array of words
  • If the number of words does not equal the length of pattern, return false immediately

2. Create Two Hash Maps

  • charToWord maps each pattern character to a word
  • wordToChar maps each word back to a pattern character
  • Two maps enforce the bijection requirement

3. Iterate Through Pattern and Words Together

  • For each index i, pair pattern[i] with words[i]

4. Check for Conflicts

  • If the character already maps to a different word, return false
  • If the word already maps to a different character, return false
  • This catches both one-to-many and many-to-one violations

5. Record the Mapping

  • Store pattern[i] -> words[i] in charToWord
  • Store words[i] -> pattern[i] in wordToChar

6. Return True

  • If the entire pattern is processed without conflicts, the string follows the pattern

Key Insight

  • This problem is essentially the same as Isomorphic Strings, but instead of mapping characters to characters, we map characters to words. The dual-map technique ensures the bijection property in both directions.
Time
O(n + m)where n is the pattern length and m is the length of string s
Space
O(n)each map stores at most n entries

Visualization

Input:
[d, o, g, , c, a, t, , c, a, t, , d, o, g]
d0o1g2 3c4a5t6 7c8a9t10 11d12o13g14
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Isomorphic Strings
Next
Happy Number