We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Word Pattern

Number: 290

Difficulty: Easy

Paid? No

Companies: Microsoft, Meta, Amazon, Zoho, Apple, Google, Bloomberg, Dropbox, Uber

Problem Description

Given a pattern string and a space-separated string s, determine if s follows the same pattern. This means there must be a bijection between each letter in the pattern and a non-empty word in s. In other words, every letter maps to exactly one unique word, and every word maps to exactly one unique letter.

Key Insights

  • We need a one-to-one mapping between characters in the pattern and words in s.
  • Use two hash maps (or dictionaries): one to map characters to words and another to map words to characters.
  • Ensure that the number of words in s equals the length of the pattern.
  • Check for any conflict during the mapping process.

Space and Time Complexity

Time Complexity: O(n) where n is the number of words (or the length of the pattern), as we iterate through both simultaneously. Space Complexity: O(n) for the mappings stored in the hash maps.

Solution

The approach is to first split the string s into words and verify that its length matches the length of the pattern. Then, iterate through each letter of the pattern along with the corresponding word, and do the following:

  1. If the pattern character is not in the char-to-word mapping, assign it, but ensure that the corresponding word is also not already assigned to a different character in the word-to-char mapping.
  2. If the pattern character already exists in the mapping, check that the mapped word matches the current word.
  3. Return false at any point a conflict is found; otherwise, return true if the entire pattern is processed without error.

This dual-check via two hash maps ensures the bijection property is maintained.

Code Solutions

# Python solution with line-by-line comments

def wordPattern(pattern: str, s: str) -> bool:
    # Split the string s based on spaces to get the list of words
    words = s.split()
    
    # If the number of words is not equal to the length of the pattern, the mapping is impossible
    if len(pattern) != len(words):
        return False
      
    # Initialize two dictionaries to maintain the mapping
    char_to_word = {}
    word_to_char = {}
    
    # Traverse each character from the pattern along with the corresponding word
    for ch, word in zip(pattern, words):
        # If the mapping for character doesn't exist, check and assign
        if ch not in char_to_word:
            if word in word_to_char:
                # Word is already mapped to a different character, hence return False
                return False
            # Create mapping in both dictionaries
            char_to_word[ch] = word
            word_to_char[word] = ch
        else:
            # If the character already has a mapping, validate it against the current word
            if char_to_word[ch] != word:
                return False
    # If all mappings are consistent, return True
    return True

# Example usage:
print(wordPattern("abba", "dog cat cat dog"))  # Expected output: True
print(wordPattern("abba", "dog cat cat fish")) # Expected output: False
← Back to All Questions