Leetcode – Word Pattern Solution in Python

In this comprehensive article, we will dive deep into a classic problem on LeetCode known as the ‘Word Pattern’. This problem is prominent in coding interviews and tests your grasp on data structures like dictionaries and sets. We will unpack the problem statement, discuss various methodologies for solving the problem, and analyze their time and space complexities.

Introduction

First, let’s review the problem statement:

You are given a pattern and a string str. You need to return True if str follows the same pattern as pattern, and False otherwise.

In the pattern, each letter stands for a distinct word in str. A word must map to exactly one letter in the pattern, and a letter must map to exactly one word.

Example:

Input: pattern = “abba”, str = “dog cat cat dog”

Output: True

Understanding the Problem

In this problem, we are given a pattern, consisting of characters, and a string of words. We have to determine whether the string follows the pattern provided. Each character in the pattern can represent a distinct word in the string, but it should be consistent throughout the string. Also, a word should only map to one character.

Basic Approach: Using Two Dictionaries

One common approach to solving this problem involves using two dictionaries to keep track of the mapping from characters to words and from words to characters.

1. Split the input string into a list of words.
2. If the number of characters in the pattern is not equal to the number of words, return False.
3. Initialize two empty dictionaries, char_to_word and word_to_char.
4. Loop through each character in the pattern and the corresponding word in the string. a. If the character is not in char_to_word, add the character and word to char_to_word and word_to_char respectively. b. If the character is in char_to_word, check if the word matches the mapping. If not, return False.
5. If the loop completes without returning False, return True.

def wordPattern(pattern, str):
    words = str.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:
            # Check if the word is already mapped to a different character
            if word in word_to_char and word_to_char[word] != char:
                return False
            char_to_word[char] = word
            word_to_char[word] = char
        elif char_to_word[char] != word:
            return False
    
    return True

Time Complexity:

O(n) – We iterate through each character and word once.

Space Complexity:

O(n) – We store the mappings in two dictionaries.

Alternative Approach: Using One Dictionary and One Set

An alternative approach involves using a single dictionary to map characters to words and a set to keep track of which words have been mapped.

1. Split the input string into a list of words.
2. If the number of characters in the pattern is not equal to the number of words, return False.
3. Initialize an empty dictionary, char_to_word, and an empty set, mapped_words.
4. Loop through each character in the pattern and the corresponding word in the string. a. If the character is not in char_to_word, add the character and word to char_to_word and mapped_words respectively after checking if the word is already in mapped_words. b. If the character is in char_to_word, check if the word matches the mapping. If not, return False.
5. If the loop completes without returning False, return True.

def wordPattern(pattern, str):
    words = str.split()
    
    if len(pattern) != len(words):
        return False
    
    char_to_word = {}
    mapped_words = set()
    
    for char, word in zip(pattern, words):
        if char not in char_to_word:
            # Check if the word is already mapped
            if word in mapped_words:
                return False
            char_to_word[char] = word
            mapped_words.add(word)
        elif char_to_word[char] != word:
            return False
    
    return True

Time Complexity:

O(n) – Similar to the first approach, we iterate through each character and word once.

Space Complexity:

O(n) – We are using a dictionary and a set to store the mappings.

Conclusion:

The Word Pattern problem on LeetCode is a quintessential example that tests one’s proficiency in utilizing data structures like dictionaries and sets to establish mappings and relationships between elements. Both of the discussed approaches offer efficient solutions in terms of time and space complexity. Being acquainted with these approaches not only assists in solving this particular problem but also lays a strong foundation for tackling other problems that involve patterns and mappings. It is advisable to thoroughly practice such problems to hone your problem-solving skills and understanding of data structures.