Of course! The "Word Pattern" problem is a classic programming puzzle that tests your ability to map relationships between two data sets (in this case, characters and words).

Here's a complete guide covering the problem statement, a Python solution, a detailed explanation, and complexity analysis.

Problem Statement

Given a pattern string and a s string, return true if s follows the pattern, and false otherwise.

What does "follow the pattern" mean?

1. Bijective Mapping (One-to-One Correspondence):

   
   （图片来源网络，侵删）
   • Every character in the pattern must map to exactly one unique word in s.
   • Every word in s must map to exactly one unique character in the pattern.

2. Structure Matching:

   • The sequence of words in s must match the sequence of characters in the pattern.

Example 1:

• pattern = "abba"
• s = "dog cat cat dog"
• Output: true
• Explanation:
  • a -> "dog"
  • b -> "cat"
  • The sequence is a, b, b, a, which maps to "dog", "cat", "cat", "dog". This matches s. The mapping is bijective.

Example 2:

• pattern = "abba"
• s = "dog cat cat fish"
• Output: false
• Explanation:
  • a -> "dog"
  • b -> "cat"
  • The sequence a, b, b, a maps to "dog", "cat", "cat", "dog". This does not match s (the last word is "fish").

Example 3:

• pattern = "aaaa"
• s = "dog cat cat dog"
• Output: false
• Explanation:
  • a cannot map to both "dog" and "cat". This violates the "one-to-one" rule.

The Python Solution

The most robust way to solve this is by using two dictionaries (or hash maps) to maintain the mappings in both directions.

def wordPattern(pattern: str, s: str) -> bool:
    """
    Determines if a string s follows a given pattern.
    Args:
        pattern: A string of characters.
        s: A string of words.
    Returns:
        True if s follows the pattern, False otherwise.
    """
    # Split the string s into a list of words
    words = s.split()
    # 1. Check for immediate length mismatch
    if len(pattern) != len(words):
        return False
    # Two dictionaries to store the character-to-word and word-to-character mappings
    char_to_word = {}
    word_to_char = {}
    # Iterate through the pattern and words simultaneously
    for char, word in zip(pattern, words):
        # Check the character-to-word mapping
        if char in char_to_word:
            # If the character is already mapped, it must map to the current word
            if char_to_word[char] != word:
                return False
        else:
            # If the character is new, it cannot map to a word that is already mapped to another character
            if word in word_to_char:
                return False
            # If the word is also new, create the mappings
            char_to_word[char] = word
            word_to_char[word] = char
    # If the loop completes without finding any inconsistencies, the pattern matches
    return True
# --- Example Usage ---
print(f"Pattern 'abba' with 'dog cat cat dog': {wordPattern('abba', 'dog cat cat dog')}")  # Output: True
print(f"Pattern 'abba' with 'dog cat cat fish': {wordPattern('abba', 'dog cat cat fish')}") # Output: False
print(f"Pattern 'aaaa' with 'dog cat cat dog': {wordPattern('aaaa', 'dog cat cat dog')}") # Output: False
print(f"Pattern 'abc' with 'b c a': {wordPattern('abc', 'b c a')}") # Output: True
print(f"Pattern 'aaa' with 'aa aa aa aa': {wordPattern('aaa', 'aa aa aa aa')}") # Output: False

Detailed Explanation of the Code

Let's break down the logic step-by-step.

Step 1: Pre-processing

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

• s.split(): This method splits the string s into a list of words, using whitespace as the delimiter. For example, "dog cat cat" becomes ['dog', 'cat', 'cat'].
• Length Check: This is a crucial optimization. If the number of characters in the pattern is not equal to the number of words in s, it's impossible for them to match. We can immediately return false.

Step 2: Data Structures for Mapping

char_to_word = {}
word_to_char = {}

We use two dictionaries to enforce the bijective (one-to-one) mapping rule.

• char_to_word: This dictionary will map a character from the pattern to its corresponding word in s. (e.g., {'a': 'dog', 'b': 'cat'})
• word_to_char: This dictionary will map a word from s to its corresponding character in the pattern. (e.g., {'dog': 'a', 'cat': 'b'})

Step 3: Iteration and Validation

for char, word in zip(pattern, words):
    # ... logic inside the loop ...

• zip(pattern, words): This is a Pythonic way to iterate over two lists (or strings) in parallel. It creates pairs of (char, word) like ('a', 'dog'), ('b', 'cat'), etc.

Step 4: The Core Logic Inside the Loop

This is the most important part. For each (char, word) pair, we need to check two things:

Case A: The character char has been seen before.

if char in char_to_word:
    if char_to_word[char] != word:
        return False

• If char is already a key in char_to_word, it means we have a rule for it. For the pattern to be valid, the current word must match the word that char was previously mapped to.
• If it doesn't match (e.g., char 'a' was mapped to 'dog', but now we see it with 'fish'), we have a conflict, and we return false.

Case B: The character char is new.

else:
    if word in word_to_char:
        return False
    char_to_word[char] = word
    word_to_char[word] = char

• If char is new, we need to create a new mapping char -> word.
• First, we check the reverse mapping: if word in word_to_char:. This ensures the word is also new. If the word is already in word_to_char, it means this word is already mapped to a different character. For example, if word is 'cat' and it's already mapped to 'b', we can't now map it to a new character 'c'. This violates the one-to-one rule, so we return false.
• If both are new, we create the two-way mappings in our dictionaries.
  • char_to_word[char] = word
  • word_to_char[word] = char

Step 5: Final Return

return True

If the for loop completes without ever returning false, it means every character and word followed the rules perfectly. Therefore, we can confidently return true.

Complexity Analysis

• Time Complexity: O(N)

  • s.split(): This takes O(M) time, where M is the length of the string s.
  • The zip and for loop iterate N times, where N is the length of the pattern (or the number of words).
  • Dictionary lookups (in operator) and insertions are, on average, O(1) time.
  • The total time is dominated by the iteration, making it O(N + M). In practice, since N and M are proportional (due to the length check), we can simplify this to O(N).

• Space Complexity: O(K)

  • Where K is the number of unique characters in the pattern.
  • We store each unique character and its corresponding word in the char_to_word dictionary.
  • We also store each unique word and its corresponding character in the word_to_char dictionary.
  • In the worst case (all characters and words are unique), K will be N. So, the space complexity is O(N).