‹ DS&A interview · Socratic
DSA · Hash Table · #187

Word Pattern

Module 54 · difficulty 2/5·⏱ 30:00starts on first keystroke

Given a `pattern` and a string `s`, find if `s` follows the same pattern. Here *follow* means a full **bijection** between a letter in `pattern` and a non-empty word in `s`: each letter maps to exactly one word, and each word maps to exactly one letter. Implement `wordPattern(pattern, s)` that returns `true` if `s` follows `pattern`, otherwise `false`. Words in `s` are separated by single spaces.

Examples
  • pattern = "abba", s = "dog cat cat dog" → true — a<->dog, b<->cat is a consistent bijection.
  • pattern = "abba", s = "dog cat cat fish" → false — a would map to both dog and fish.
  • pattern = "aaaa", s = "dog cat cat dog" → false — a maps to dog and cat — not a function.
Constraints
  • · 1 <= pattern.length <= 300
  • · pattern contains only lowercase English letters.
  • · 1 <= s.length <= 3000
  • · s contains only lowercase English letters and single spaces.
  • · s does not contain leading or trailing spaces.
  • · Words in s are separated by a single space.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.