NUHMAN.com

Introduction

LeetCode 290: Word Pattern is a problem that asks you to determine whether a given string pattern matches a sequence of words. The main challenge is to ensure that there is a one-to-one mapping between the characters in the pattern and the words in the string.

The problem requires checking if there is a bijection (one-to-one and onto function) between the characters in the pattern and the words in the string, meaning:

• Each character in the pattern must correspond to exactly one word.
• Each word in the string must correspond to exactly one character in the pattern.

Problem Statement

Given a string pattern and a string s, return true if there is a one-to-one correspondence between the characters in pattern and the words in s.

You need to check if the pattern matches the words in the string such that:

• Each character in pattern maps to exactly one word in s.
• Each word in s maps to exactly one character in pattern.

Example

python

Input:
pattern = "abba"
s = "dog cat cat dog"

Output:
true

Explanation:
The pattern "abba" matches the words in the string "dog cat cat dog" as follows:
'a' -> "dog"
'b' -> "cat"
'b' -> "cat"
'a' -> "dog"
python

Input:
pattern = "abba"
s = "dog cat cat fish"

Output:
false

Explanation:
The pattern "abba" does not match the words in the string "dog cat cat fish" because:
'a' -> "dog" and 'b' -> "cat", but 'b' does not map to "fish".

✅ Step-by-Step Solution

🧠 Intuition

The problem boils down to checking if the characters in the pattern can be uniquely mapped to the words in the string and vice versa. The mapping must be:

1. One-to-One: Each character in the pattern maps to exactly one word, and each word maps to exactly one character.
2. Bijective: The mapping between the characters and words should be consistent for the entire string.

To achieve this, we can use two hashmaps (dictionaries):

• One to map characters in the pattern to words in the string.
• Another to map words to characters to ensure the reverse mapping is valid.

✅ Approach

1. Split the String:

• Split the string s into individual words.

1. Check Length Consistency:

• The length of the pattern should match the number of words in the string. If not, return false.

1. Check the Mappings:

• Iterate through the characters in the pattern and the words in the string.
• For each character, check if it is already mapped to a word:
• If it is, the word must match the current word in the string.
• If it is not, add the character-to-word mapping.
• Similarly, ensure that no two characters map to the same word using the reverse mapping.

1. Return the Result:

• If any mapping violates the constraints, return false. Otherwise, return true.

✅ Python Code

python

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()  # Split the string into words
        if len(pattern) != len(words):
            return False  # Pattern and word count must be the same
        
        char_to_word = {}  # Mapping from pattern character to word
        word_to_char = {}  # Mapping from word to pattern character
        
        for p, w in zip(pattern, words):
            if p in char_to_word:
                if char_to_word[p] != w:  # If already mapped to a different word
                    return False
            else:
                char_to_word[p] = w
                
            if w in word_to_char:
                if word_to_char[w] != p:  # If already mapped to a different character
                    return False
            else:
                word_to_char[w] = p
                
        return True

🧪 How It Works

1. Split the String:

• We first split the string s into a list of words.

1. Check Length:

• If the length of the pattern and the number of words don't match, return false immediately.

1. Mapping Characters to Words:

• We use two dictionaries:
• char_to_word to map a character from the pattern to a word.
• word_to_char to map a word to a character from the pattern.
• As we iterate through the pattern and words, we check for any conflicts:
• If a character in the pattern is already mapped to a different word than expected, return false.
• If a word is already mapped to a different character than expected, return false.

1. Return the Result:

• If no conflicts are found, the function returns true, indicating a valid mapping exists.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n), where n is the length of the pattern or the number of words (since we iterate through the pattern and words once).Space ComplexityO(n), where n is the number of words, due to the two dictionaries used to store the mappings.

• The time complexity is linear because we are iterating through the pattern and the list of words once.
• The space complexity is also linear because we store up to n characters and words in the mappings.

🔍 Edge Cases

1. Different Lengths: If the length of pattern does not match the number of words in the string, return false.
2. Empty String and Pattern: If both the pattern and the string are empty, return true, as they trivially match.
3. Pattern with Repeated Characters: The mapping should still be valid as long as the repeated characters map to the same word. For example, "aab" → "cat cat dog".
4. String with Extra or Fewer Words: If the string has more or fewer words than expected based on the pattern, return false.

✅ Conclusion

LeetCode 290: Word Pattern is a problem that involves checking if there is a one-to-one correspondence between characters in a pattern and words in a string. The solution uses two hashmaps to ensure that the mappings are consistent both ways — from pattern to words and from words to pattern. This solution is efficient with a time complexity of O(n) and space complexity of O(n).

This problem is a good practice for understanding bijective mappings and string manipulation.