Word Pattern - Solution & Explanation
Problem Statement
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
patternmaps to exactly one unique word ins. - Each unique word in
smaps to exactly one letter inpattern. - No two letters map to the same word, and no two words map to the same letter.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
The bijection can be established as:
'a'maps to"dog".'b'maps to"cat".
Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Constraints:
1 <= pattern.length <= 300patterncontains only lower-case 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.
Approach Overview
Problem Overview: You are given a pattern string and a space-separated sentence. The task is to determine whether the sentence follows the same pattern. Each character in the pattern must map to exactly one word in the sentence, and no two characters can map to the same word.
This is a classic bijection validation problem. You must ensure a one-to-one relationship between pattern characters and words. Problems like this frequently rely on hash table lookups and efficient string processing.
Approach 1: Hash Map Mapping (O(n) time, O(n) space)
The most direct solution uses two hash maps to enforce a bijection between pattern characters and words. Split the sentence into words, then iterate through both the pattern and word list simultaneously. One map stores char ā word and another stores word ā char. During iteration, verify that existing mappings remain consistent. If a mismatch appears, return false immediately. Hash lookups make each check constant time, so the overall runtime is O(n) where n is the number of words. This approach is easy to reason about and mirrors how interviewers expect you to validate one-to-one mappings.
Approach 2: Index Mapping (O(n) time, O(n) space)
Instead of storing explicit mappings, track the last index where each pattern character and word appeared. Use two maps: char ā last index and word ā last index. As you iterate through the sequence, compare the stored indices for the current character and word. If they differ, the pattern relationship is broken. If they match, update both with the current index. This works because valid pairs must always appear at the same positions in their respective sequences. The method still runs in O(n) time with O(n) space but avoids storing full string mappings.
Recommended for interviews: The hash map mapping approach is the most common answer because it clearly demonstrates understanding of bijection constraints. Interviewers expect candidates to enforce both directions of the mapping. The index mapping technique is a clever alternative that reduces conceptual overhead once you recognize the pattern of comparing last-seen indices.
Approach 1: Approach 1: Hash Map Mapping
This approach uses two hash maps (dictionaries) to establish bijective mappings between characters in the pattern and words in the string. One map tracks the character to word mapping, while the other tracks word to character mapping. During iteration, we update or check both maps to ensure the bijection property holds.
The solution creates two mappings using arrays, tracking which pattern character maps to each word and vice versa. During each step, the program checks if the current word and character have conflicting existing mappings.
Complexity
Time Complexity: O(n + m), where n is the length of the pattern and m is the length of the string. Each space-separated word in s is checked at least once.
Space Complexity: O(n + m) for storing the mapping of characters to words and words to characters.
Approach 2: Approach 2: Index Mapping
The index mapping approach ensures that the last seen indexes of each character in the pattern and each word from s match. By tracking their last occurrences, you can simplify identifying mismatched patterns in linear time.
This C implementation uses two arrays to track the last-occurring index in pattern and s. With words stored in an array, index comparisons determine if the words and pattern characters have been alternating in previously unseen sequences.
Complexity
Time Complexity: O(n + m), where n is the pattern length and m is sā length.
Space Complexity: O(n + m) concerning the arrays holding the last occurring indices.
Approach 3: Hash Table
First, we split the string s into a word array ws with spaces. If the length of pattern and ws is not equal, return false directly. Otherwise, we use two hash tables d_1 and d_2 to record the correspondence between each character and word in pattern and ws.
Then, we traverse pattern and ws. For each character a and word b, if there is a mapping for a in d_1, and the mapped word is not b, or there is a mapping for b in d_2, and the mapped character is not a, return false. Otherwise, we add the mapping of a and b to d_1 and d_2 respectively.
After the traversal, return true.
The time complexity is O(m + n) and the space complexity is O(m + n). Here m and n are the length of pattern and string s.
Approach 4: Default Approach
Code
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map Mapping | Time Complexity: O(n + m), where n is the length of the pattern and m is the length of the string. Each space-separated word in |
| Approach 2: Index Mapping | Time Complexity: O(n + m), where n is the pattern length and m is sā length. |
| Hash Table | ā |
| Default Approach | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Mapping | O(n) | O(n) | General case when validating one-to-one mapping between two sequences |
| Index Mapping | O(n) | O(n) | When you want a concise solution using last-seen index comparisons |
Video Solution
Word Pattern - Leetcode 290 - Python ā¢ NeetCode ā¢ 51,949 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Word Pattern easy or hard?
Word Pattern Python/Java solution
How to solve Word Pattern in O(n)?
What is the best approach for Word Pattern?
Is Word Pattern asked at Google/Amazon/Meta?
What data structure is used in Word Pattern?
What is the time complexity of Word Pattern?
Ready to solve this problem?
Practice Word Pattern with our built-in code editor and test cases.
Practice on FleetCode