The Word Pattern problem is a common string manipulation challenge often asked in coding interviews. It tests your understanding of pattern matching and string mapping.
In this article, we will break down the problem, explain the approach, walk through the JavaScript solution, and provide some notes for better clarity.
Given a string pattern and a string s, return true if s follows the same pattern.
Here’s how the pattern matching works:
Each letter in the pattern corresponds to a word in the string s.
Each letter in the pattern must map to a unique word and vice versa.
The length of the pattern and the number of words in s must be the same.
The letters in the pattern map uniquely to words in s and vice versa.
wordPattern("abba", "dog cat cat dog"); // true
wordPattern("abba", "dog cat cat fish"); // false
wordPattern("aaaa", "dog cat cat dog"); // false
wordPattern("abba", "dog dog dog dog"); // false
To determine if s follows the same pattern as pattern, we need to establish a one-to-one mapping between the characters in the pattern and the words in the string s.
Length Mismatch: If the length of pattern doesn’t match the number of words in s, return false immediately.
One-to-One Mapping: Each character in pattern must map to a unique word, and no two characters in pattern can map to the same word.
Reverse Mapping: Similarly, each word in s must map to a unique character in pattern.
The best solution to this problem is to use two hash maps (or objects) to store the mappings from pattern to words and from words to pattern. This ensures a one-to-one mapping in both directions.
/**
* Determines if string `s` follows the same pattern as `pattern`.
* @param {string} pattern - The pattern string.
* @param {string} s - The string to check.
* @return {boolean}
*/
var wordPattern = function(pattern, s) {
const words = s.split(' ');
if (pattern.length !== words.length) return false;
const mapPatternToWord = new Map();
const mapWordToPattern = new Map();
for (let i = 0; i < pattern.length; i++) {
const char = pattern[i];
const word = words[i];
if (mapPatternToWord.has(char)) {
if (mapPatternToWord.get(char) !== word) return false;
} else {
mapPatternToWord.set(char, word);
}
if (mapWordToPattern.has(word)) {
if (mapWordToPattern.get(word) !== char) return false;
} else {
mapWordToPattern.set(word, char);
}
}
return true;
};
Step 1: First, split the string s into individual words.
Step 2: Check if the length of the pattern matches the number of words. If not, return false.
Step 3: Use two hash maps (mapPatternToWord and mapWordToPattern) to track the mappings between characters and words.
Step 4: For each character in pattern and the corresponding word in s, ensure the mappings are consistent.
If the character has been seen before and doesn’t map to the same word, return false.
Similarly, ensure the word hasn’t been mapped to a different character.
Step 5: If all checks pass, return true.
Time Complexity: O(n), where n is the length of the pattern (or the number of words in s). The loop iterates through the string once, and each operation inside the loop (like getting and setting values in the map) takes constant time.
Space Complexity: O(n), for the space used by the two maps.
✅ Case Sensitivity: This problem is case-sensitive, meaning “a” and “A” are treated as different characters.
✅ Multiple Spaces: Ensure there are no extra spaces in the string s, as splitting s with .split(' ') will treat consecutive spaces as empty words.
✅ Uniqueness Check: Both maps ensure that the mappings are one-to-one and unique.
❌ Order Matters: The order of characters in pattern and words in s must match exactly.
✅ Edge Cases: Consider edge cases like empty strings or strings with different lengths.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Approach | O(n) | O(n) |