Watch 10 video solutions for Word Pattern, a easy level problem involving Hash Table, String. This walkthrough by Ashish Pratap Singh has 1,002,123 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
pattern maps to exactly one unique word in s.s maps to exactly one letter in pattern.
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 <= 300pattern contains only lower-case English letters.1 <= s.length <= 3000s contains only lowercase English letters and spaces ' '.s does not contain any leading or trailing spaces.s are separated by a single space.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 | 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 |