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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Word Pattern and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →