Skip to main content

290. Word Pattern

easy

Given a pattern like 'abba' and a string 'dog cat cat dog', decide whether the words follow the same letter pattern. The real test is remembering you need a TWO-hash equality check — one map each direction — to reject collisions like ('abba', 'dog cat cat fish') and ('aaaa', 'dog cat cat dog').

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a pattern and a string s, find if s follows the same pattern. Here follow 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.

Constraints

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

Examples

Example 1

Input
pattern = 'abba', s = 'dog cat cat dog'
Output
true

Example 2

Input
pattern = 'abba', s = 'dog cat cat fish'
Output
false

Example 3

Input
pattern = 'aaaa', s = 'dog cat cat dog'
Output
false

Explanation: Pattern letter 'a' would have to map to both 'dog' and 'cat'.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Split s on spaces. If the word count doesn't equal pattern.length, return false immediately.

Hint 2

A single map letter -> word is not enough — it accepts ('aaaa', 'dog cat cat dog') because no letter ever conflicts.

Hint 3

Keep TWO maps: letter -> word AND word -> letter. For each (letter, word) pair, if either map has a conflicting entry, return false. Otherwise insert both.

Solution approach

Reveal approach

Two-hash equality test. Tokenize s by splitting on spaces and verify words.length == pattern.length. Walk the two sequences in parallel. Maintain two maps: letterToWord (char -> string) and wordToLetter (string -> char). For each index i, look up both maps. If letter already maps to a different word, or word already maps to a different letter, return false. Otherwise record both mappings. The two-direction check is the moat — a one-way map silently accepts collisions where two different letters map to the same word.

Complexity

Time
O(n + m)
Space
O(n + m)

Related patterns

  • hash-map
  • two-hash-equality-test

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Uber
  • Capital One

More Hash Tables practice problems

See all Hash Tables problems →