[LeetCode/Python] 290. Word Pattern

📌 Problem

[LeetCode] 290. Word Pattern

📌 Solution

Solution 1: Bidirectional Mapping

Idea

• Split s into words
• Maintain two hash maps: pattern → word, word → pattern

Code

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()

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

        p2w, w2p = {}, {}
        for a, b in zip(pattern, words):
            if a in p2w and b != p2w[a]:
                return False
            if b in w2p and a != w2p[b]:
                return False
            p2w[a] = b
            w2p[b] = a

        return True

Complexity

• Time: $O(n)$ where $n$ = len(pattern) (or number of words)
• Space: $O(k)$ where $k$ = number of unique letters + words

Solution 2:

Idea

• Split s into words
• Compare uniqueness counts:
  - len(set(pattern))
  - len(set(words))
  - len(set(zip(pattern, words)))
• If all equal → bijection exists

Code

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        return (
            len(pattern) == len(words)
            and len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words)))
        )

Complexity

• Time: $O(1)$ (Hash/dict/set operations are amortized)
• Space: $O(k)$ for the three sets, slightly higher constant factor