Sponsored
Sponsored
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.
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.
1function wordPattern(pattern, s) {
2 const words = s.split(' ');
3 if (pattern.length !== words.length) return false;
4
5 const charToWord = new Map();
6 const wordToChar = new Map();
7
8 for (let i = 0; i < pattern.length; i++) {
9 const char = pattern[i];
10 const word = words[i];
11
12 if (charToWord.has(char) && charToWord.get(char) !== word) return false;
13 if (wordToChar.has(word) && wordToChar.get(word) !== char) return false;
14
15 charToWord.set(char, word);
16 wordToChar.set(word, char);
17 }
18 return true;
19}
20
21console.log(wordPattern("abba", "dog cat cat dog")); // true
22In JavaScript, the Map object helps maintain key-value links between characters and words. The code ensures bidirectional check to enforce bijective mapping, verifying for existing contradictions.
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.
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.
1
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.