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.
1def wordPattern(pattern: str, s: str) -> bool:
2 words = s.split()
3 if len(pattern) != len(words):
4 return False
5 char_to_word = {}
6 word_to_char = {}
7 for char, word in zip(pattern, words):
8 if char in char_to_word and char_to_word[char] != word:
9 return False
10 if word in word_to_char and word_to_char[word] != char:
11 return False
12 char_to_word[char] = word
13 word_to_char[word] = char
14 return True
15
16print(wordPattern("abba", "dog cat cat dog")) # True
17This Python code uses two dictionaries to track mappings between pattern characters and words. The split words get compared with the characters, with validations set to ensure correct relations in both mappings.
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.