Word Pattern
The key idea
A valid pattern is a two-way (bijective) mapping: each pattern letter binds to exactly one word AND each word binds to exactly one letter. Track both directions in two hash maps and reject the first time either binding contradicts a previous one.
Problem
You are given a pattern and a string s. Return true 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.
The i-th letter of pattern lines up with the i-th word of s, where the words of s are separated by single spaces.
Constraints
1 <= pattern.length <= 300patterncontains only lowercase English letters.1 <= s.length <= 3000scontains only lowercase English letters and spaces' '.sdoes not contain any leading or trailing spaces.- All the words in
sare separated by a single space.
Examples
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Complexity
Time: O(n + m) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Contains Duplicate IIEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY