Solution Explanation for LeetCode 290: Word Pattern

This problem checks if a given pattern of characters matches a string of words, where each character in the pattern corresponds to a unique word in the string, and vice versa. This requires a bijective mapping (one-to-one correspondence) between characters and words.

Approach: Using Hash Maps (Dictionaries)

The most efficient approach utilizes two hash maps (or dictionaries):

1. pattern_map: Maps characters from the pattern string to words from the s string.
2. word_map: Maps words from the s string to characters from the pattern string.

These maps ensure that the one-to-one correspondence is maintained during the comparison.

Algorithm:

1. Split the string s: Split the input string s into an array of words using whitespace as the delimiter.
2. Check lengths: If the length of the pattern and the number of words in s are different, return false immediately (because a bijection is impossible).
3. Iterate and check: Iterate through both the pattern and the words array simultaneously. For each character-word pair:
   • If the character is already in pattern_map and it maps to a different word, return false.
   • If the word is already in word_map and it maps to a different character, return false.
   • Otherwise, add the mapping to both pattern_map and word_map.
4. Return true: If the loop completes without finding any conflicts, it means a bijective mapping exists, and the function returns true.

Code Implementation (Python):

def wordPattern(pattern: str, s: str) -> bool:
    words = s.split()
    if len(pattern) != len(words):
        return False
 
    pattern_map = {}
    word_map = {}
 
    for char, word in zip(pattern, words):
        if char in pattern_map and pattern_map[char] != word:
            return False
        if word in word_map and word_map[word] != char:
            return False
        pattern_map[char] = word
        word_map[word] = char
 
    return True
 

Time and Space Complexity Analysis:

• Time Complexity: O(N), where N is the length of the pattern string (or equivalently, the number of words in s). This is because we iterate through the strings once.
• Space Complexity: O(N) in the worst case, as the hash maps could potentially store up to N entries (if all characters and words are unique). In practice, it's often less than O(N) if there are repetitions.

Other Language Examples:

The core logic remains the same across different programming languages; only the syntax for hash maps/dictionaries varies. The other examples provided in the original response demonstrate this consistency. For instance, Java uses HashMap, C++ uses unordered_map, etc., but all follow the same algorithmic steps.

This solution offers a clear, concise, and efficient way to solve the Word Pattern problem. The use of hash maps optimizes the lookup time for checking existing mappings, ensuring a linear time complexity.