Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0290 - Word Pattern
    0290 - Word Pattern
    0290 - Word Pattern
    0290 - Word Pattern

    0290 - Word Pattern

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/word-pattern/

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: 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()

    """ 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()