Solution 1 - Two Dictionary Bijection

Given a pattern and a string s, determine if s follows the same pattern. This means there must be a bijection (one-to-one mapping) between each letter in pattern and each word in s. We use two hash maps to track the mapping in both directions — pattern → word and word → pattern — ensuring no two letters map to the same word and vice versa.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0290.1 - Solution 1 - Two Dictionary Bijection """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def wordPattern(self, pattern: str, s: str) -> bool:
        """Word Pattern Function"""
        words = s.split()

        if len(pattern) != len(words):
            return False

        char_to_word = {}
        word_to_char = {}

        for char, word in zip(pattern, words):
            if char in char_to_word:
                if char_to_word[char] != word:
                    return False
            else:
                char_to_word[char] = word

            if word in word_to_char:
                if word_to_char[word] != char:
                    return False
            else:
                word_to_char[word] = char

        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().wordPattern("abba", "dog cat cat dog"))       # True
    print(Solution().wordPattern("abba", "dog cat cat fish"))      # False
    print(Solution().wordPattern("aaaa", "dog cat cat dog"))       # False
    print(Solution().wordPattern("abba", "dog dog dog dog"))       # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Index Mapping

Instead of maintaining two dictionaries, map each character and each word to the index of their first occurrence. If at any position the first-occurrence index of the character differs from that of the word, the pattern does not match.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0290.2 - Solution 2 - Index Mapping """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def wordPattern(self, pattern: str, s: str) -> bool:
        """Word Pattern Function"""
        words = s.split()

        if len(pattern) != len(words):
            return False

        return [pattern.index(c) for c in pattern] == [words.index(w) for w in words]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().wordPattern("abba", "dog cat cat dog"))       # True
    print(Solution().wordPattern("abba", "dog cat cat fish"))      # False
    print(Solution().wordPattern("aaaa", "dog cat cat dog"))       # False
    print(Solution().wordPattern("abba", "dog dog dog dog"))       # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0290 - Word Pattern

Solution 1 - Two Dictionary Bijection

Solution 2 - Index Mapping