Problem Description

You are given a pattern string and a string s. You need to determine if s follows the same pattern.

For s to follow the pattern, there must be a bijection (one-to-one correspondence) between each letter in pattern and each word in s. This means:

• Each letter in pattern must map to exactly one unique word in s. For example, if letter 'a' maps to word "dog", then every occurrence of 'a' must correspond to "dog".

• Each unique word in s must map to exactly one letter in pattern. For example, if word "dog" maps to letter 'a', then every occurrence of "dog" must correspond to 'a'.

• No two different letters can map to the same word, and no two different words can map to the same letter.

The string s contains words separated by spaces, and each word is non-empty.

Example:

• If pattern = "abba" and s = "dog cat cat dog", this would return true because:

  • 'a' maps to "dog"
  • 'b' maps to "cat"
  • The pattern abba corresponds to dog cat cat dog

• If pattern = "abba" and s = "dog cat cat fish", this would return false because:

  • 'a' would need to map to both "dog" and "fish", which violates the bijection rule

The solution uses two hash tables to track the bidirectional mapping between pattern characters and words, ensuring that the bijection property is maintained throughout the traversal.

Intuition

The key insight is recognizing that we need to maintain a bidirectional mapping between pattern characters and words. Think of it like a translation dictionary that works both ways - if we know that 'a' translates to "dog", then "dog" must always translate back to 'a'.

Why do we need two hash tables instead of just one? Consider this scenario:

• If we only track that 'a' -> "dog" and 'b' -> "dog", we wouldn't catch the error that two different letters map to the same word.
• Similarly, if pattern is "aa" and string is "dog cat", using only one mapping wouldn't detect that the same letter 'a' is trying to map to two different words.

The bidirectional check ensures both conditions of the bijection are satisfied:

1. Forward mapping (d1): Ensures each pattern character consistently maps to the same word
2. Reverse mapping (d2): Ensures each word consistently maps to the same pattern character

As we iterate through the pattern and words simultaneously using zip, we check:

• If we've seen this pattern character before (a in d1), does it still map to the same word?
• If we've seen this word before (b in d2), does it still map to the same pattern character?

If either check fails, we know the bijection is broken. If we successfully process all pairs without conflicts, the pattern matches.

The initial length check (len(pattern) != len(ws)) is a quick optimization - if the pattern has a different number of characters than we have words, there's no possible valid mapping.

Solution Approach

The implementation uses two hash tables to maintain the bidirectional mapping between pattern characters and words.

Step 1: Split and Length Check

ws = s.split()
if len(pattern) != len(ws):
    return False

First, we split the string s by spaces to get a list of words ws. If the number of pattern characters doesn't match the number of words, we immediately return False since a valid bijection is impossible.

Step 2: Initialize Two Hash Tables

d1 = {}  # Maps pattern character -> word
d2 = {}  # Maps word -> pattern character

• d1 tracks the mapping from each character in the pattern to its corresponding word
• d2 tracks the reverse mapping from each word to its corresponding pattern character

Step 3: Iterate and Validate Mappings

for a, b in zip(pattern, ws):
    if (a in d1 and d1[a] != b) or (b in d2 and d2[b] != a):
        return False
    d1[a] = b
    d2[b] = a

For each pair (a, b) where a is a pattern character and b is a word:

1. Check for conflicts:
   • If a already exists in d1 but maps to a different word than b, the pattern is violated
   • If b already exists in d2 but maps to a different character than a, the pattern is violated
2. Update mappings: If no conflicts are found, we establish or confirm the mappings:
   • d1[a] = b: Character a maps to word b
   • d2[b] = a: Word b maps to character a

Step 4: Return Success If we complete the iteration without finding any conflicts, return True.

Time Complexity: O(n + m) where n is the length of the pattern and m is the length of string s (for splitting)

Space Complexity: O(n) for storing the mappings in both hash tables, where at most we store n unique mappings

Example Walkthrough

Let's walk through the solution with pattern = "abb" and s = "cat dog dog".

Step 1: Split and Length Check

• Split s into words: ws = ["cat", "dog", "dog"]
• Check lengths: len(pattern) = 3, len(ws) = 3 ✓ (equal, continue)

Step 2: Initialize Hash Tables

• d1 = {} (pattern char → word)
• d2 = {} (word → pattern char)

Step 3: Process Each Pair

Iteration 1: a = 'a', b = "cat"

• Check: Is 'a' in d1? No. Is "cat" in d2? No.
• No conflicts found, update mappings:
  • d1 = {'a': "cat"}
  • d2 = {"cat": 'a'}

Iteration 2: a = 'b', b = "dog"

• Check: Is 'b' in d1? No. Is "dog" in d2? No.
• No conflicts found, update mappings:
  • d1 = {'a': "cat", 'b': "dog"}
  • d2 = {"cat": 'a', "dog": 'b'}

Iteration 3: a = 'b', b = "dog"

• Check:
  • Is 'b' in d1? Yes. Does d1['b'] == "dog"? Yes ✓
  • Is "dog" in d2? Yes. Does d2["dog"] == 'b'? Yes ✓
• No conflicts found, mappings remain:
  • d1 = {'a': "cat", 'b': "dog"}
  • d2 = {"cat": 'a', "dog": 'b'}

Step 4: Return Result All pairs processed without conflicts → Return True

Counter-example: If we had pattern = "abb" and s = "cat dog cat":

• At iteration 3: a = 'b', b = "cat"
• Check: 'b' is in d1 and d1['b'] = "dog", but b = "cat"
• Conflict detected ("dog" != "cat") → Return False

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the length of the pattern string and n is the length of string s.

• Splitting string s by spaces takes O(n) time as it needs to traverse the entire string.
• The zip operation combined with the loop iterates through min(pattern length, words length) elements, which is at most O(m) iterations after the length check.
• Inside each iteration, dictionary lookups and insertions (in operator and assignment) take O(1) average time.
• Therefore, the overall time complexity is O(n) for splitting + O(m) for the loop = O(m + n).

Space Complexity: O(m + n), where m is the length of the pattern string and n is the length of string s.

• The ws list stores all words from string s, which takes O(n) space in the worst case (when s contains no spaces, the entire string is one word).
• Dictionary d1 stores at most m key-value pairs (pattern characters to words), requiring O(m) space for keys plus the space for word values.
• Dictionary d2 stores at most m key-value pairs (words to pattern characters), requiring space for word keys plus O(m) space for character values.
• The total space used by both dictionaries is proportional to the number of unique pattern characters and unique words, bounded by O(m + n).
• Therefore, the overall space complexity is O(m + n).

Common Pitfalls

Pitfall: Using Only One Hash Table

A frequent mistake is using only a single hash table to map pattern characters to words, without checking the reverse mapping. This approach fails to ensure a proper bijection.

Incorrect Implementation:

def wordPattern(self, pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words):
        return False
  
    pattern_to_word = {}
  
    for pattern_char, word in zip(pattern, words):
        if pattern_char in pattern_to_word:
            if pattern_to_word[pattern_char] != word:
                return False
        else:
            pattern_to_word[pattern_char] = word
  
    return True

Why This Fails: This implementation only checks if each pattern character maps consistently to the same word, but doesn't verify that different pattern characters map to different words.

Failing Test Case:

• Input: pattern = "abba", s = "dog dog dog dog"
• The incorrect code returns True (both 'a' and 'b' map to "dog")
• Expected output: False (violates bijection - two different letters cannot map to the same word)

Solution: Always use two hash tables to maintain bidirectional mapping:

1. One mapping from pattern characters to words (pattern_to_word)
2. One mapping from words to pattern characters (word_to_pattern)

This ensures that:

• No two different pattern characters map to the same word
• No two different words map to the same pattern character

The correct implementation checks both directions of the mapping, guaranteeing a true one-to-one correspondence between pattern characters and words.