Domain 1EasyCORE

Word Pattern

The problem asks us to determine if a given string `s` follows the same pattern as described by another string `pattern`. The pattern consists of lowercase English letters, and `s` consists of words separated by spaces. A bijection means that each character in the pattern must map to exactly one word in `s`, and vice versa.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

290. Word Pattern

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 38.4%


Problem Breakdown

The problem asks us to determine if a given string s follows the same pattern as described by another string pattern. The pattern consists of lowercase English letters, and s consists of words separated by spaces. A bijection means that each character in the pattern must map to exactly one word in s, and vice versa.

Inputs:

  • pattern: a string containing only lowercase English letters.
  • s: a string containing words separated by single spaces.

Outputs:

  • A boolean value indicating whether s follows the same pattern as pattern.

Implicit Constraints or Tricky Edge Cases:

  • The lengths of pattern and s are within specified bounds (1 to 300 for pattern, 1 to 3000 for s).
  • s does not contain leading or trailing spaces, and all words are separated by a single space.
  • Edge cases include patterns with repeated characters and strings with repeated words.

Intuition

A brute-force approach would involve checking every possible mapping of characters in the pattern to words in s, which is computationally expensive. Instead, we can use a hash table (dictionary) to establish a bijection between characters in the pattern and words in s. This allows us to efficiently check if the mapping holds for the entire string.

The key insight is that both the pattern and the words in s should have a one-to-one correspondence. If a character in the pattern maps to more than one word or vice versa, the strings do not follow the same pattern.

Approach

  1. Split the string s into a list of words.
  2. Check if the length of the pattern matches the number of words in s. If not, return false.
  3. Use two hash tables (dictionaries):
    • One to map characters from the pattern to words in s.
    • Another to map words in s to characters in the pattern.
  4. Iterate through each character in the pattern and its corresponding word:
    • If the character is not already mapped, create a new mapping in both hash tables.
    • If the character is already mapped, check if it maps to the current word. If not, return false.
  5. After processing all characters, if no inconsistencies are found, return true.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the pattern (or equivalently, the number of words in s). We iterate through each character and word once.
  • Space Complexity: O(m + k), where m is the number of unique characters in the pattern and k is the number of unique words in s. This accounts for the space used by the two hash tables.

Solution

def wordPattern(pattern: str, s: str) -> bool:
    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 not in char_to_word and word not in word_to_char:
            char_to_word[char] = word
            word_to_char[word] = char
        elif char_to_word.get(char) != word or word_to_char.get(word) != char:
            return False
    
    return True

Edge Cases Handled

  • Pattern with repeated characters: The code ensures that each character maps to exactly one word.
  • String with repeated words: Similarly, each word must map to exactly one character.
  • Different lengths of pattern and string: If the lengths do not match, the function immediately returns false.
  • Empty input: Although the constraints specify minimum lengths, if both inputs were empty, the function would return true since there are no characters or words to mismatch.