Introduction

In this blog post, we will explore how to solve the LeetCode problem "290" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given a pattern and a string s, find if s follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically: Each letter in pattern maps to exactly one unique word in s. Each unique word in s maps to exactly one letter in pattern. No two letters map to the same word, and no two words map to the same letter. Example 1: Input: pattern = "abba", s = "dog cat cat dog" Output: true Explanation: The bijection can be established as: 'a' maps to "dog". 'b' maps to "cat". Example 2: Input: pattern = "abba", s = "dog cat cat fish" Output: false Example 3: Input: pattern = "aaaa", s = "dog cat cat dog" Output: false Constraints: 1 <= pattern.length <= 300 pattern contains only lower-case English letters. 1 <= s.length <= 3000 s contains only lowercase English letters and spaces ' '. s does not contain any leading or trailing spaces. All the words in s are separated by a single space.

Explanation

Here's the approach:

• Use Hash Maps for Bijective Mapping: Maintain two hash maps (dictionaries in Python). One maps characters in the pattern to words in s, and the other maps words in s back to characters in pattern.
• Ensure One-to-One Correspondence: Before adding a new mapping, check if the character or word is already mapped to a different value. If it is, it violates the bijection property, and we return False.

• Check Lengths: Ensure the number of characters in the pattern matches the number of words in the string.

• Runtime Complexity: O(N), where N is the length of the pattern (or the number of words in the string).

• Storage Complexity: O(M), where M is the number of unique characters in the pattern and unique words in the string.

Code

    def word_pattern(pattern: str, s: str) -> bool:
    """
    Given a pattern and a string s, find if s follows the same pattern.

    Args:
        pattern: The pattern string.
        s: The input string.

    Returns:
        True if s follows the pattern, False otherwise.
    """

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

    pattern_map = {}
    word_map = {}

    for i in range(len(pattern)):
        char = pattern[i]
        word = words[i]

        if char in pattern_map:
            if pattern_map[char] != word:
                return False
        else:
            if word in word_map:
                if word_map[word] != char:
                    return False
            else:
                pattern_map[char] = word
                word_map[word] = char

    return True