LeetCode 290 - Word Pattern

The problem gives two inputs: a pattern string and a space-separated string of words. We need to determine whether the sequence of words follows the same structure as the sequence of characters in the pattern.

leetcodeeasyhash-tablestring

LeetCode Problem 290

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem gives two inputs: a pattern string and a space-separated string of words. We need to determine whether the sequence of words follows the same structure as the sequence of characters in the pattern.

A valid match requires a bijection between pattern characters and words. A bijection means the mapping works in both directions:

  • Each character maps to exactly one word.
  • Each word maps to exactly one character.

This condition is stricter than simply checking whether every character consistently maps to the same word. We must also ensure that two different characters do not map to the same word.

For example, with pattern "abba" and string "dog cat cat dog":

  • 'a' maps to "dog"
  • 'b' maps to "cat"

The mapping is consistent and unique in both directions, so the answer is true.

However, for pattern "abba" and string "dog dog dog dog":

  • 'a' would map to "dog"
  • 'b' would also map to "dog"

This violates the bijection requirement because two different pattern characters map to the same word.

The constraints are relatively small. The pattern length is at most 300, and the string length is at most 3000. This means even moderately inefficient approaches would still run fast enough, but the problem is fundamentally designed to test correct hash map usage and understanding of bijections.

Several edge cases are important:

  • The number of pattern characters may not equal the number of words.
  • A character may appear multiple times and must always map to the same word.
  • Different characters must not map to the same word.
  • The input guarantees valid formatting, meaning there are no extra spaces and every word is non-empty.

These guarantees simplify parsing because splitting the string by spaces always produces valid words.

Approaches

A brute-force solution could repeatedly scan all previous mappings every time we process a new character-word pair. For each position, we would check whether the current character was previously associated with a different word or whether the current word was previously associated with a different character.

This works because every pair is validated against all earlier pairs, ensuring consistency. However, the repeated scanning makes the solution inefficient. If the pattern length is n, we may compare each pair against up to n earlier entries, producing quadratic time complexity.

The key observation for an optimal solution is that we need constant-time lookup in both directions. A hash map is ideal for this because it allows quick verification of existing mappings.

We maintain:

  • A map from pattern character to word
  • A map from word to pattern character

When processing each pair:

  • If the character already exists in the first map, its mapped word must match the current word.
  • If the word already exists in the second map, its mapped character must match the current character.

If either condition fails, the pattern is invalid.

This approach ensures every mapping decision is checked immediately in constant time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly scans previous mappings for consistency
Optimal O(n) O(n) Uses two hash maps for constant-time bidirectional checks

Algorithm Walkthrough

  1. Split the input string s into a list of words.

We need direct positional access because each pattern character corresponds to exactly one word at the same index. 2. Compare the number of words with the length of the pattern.

If they differ, the mapping is impossible. Every character must map to exactly one word, so the counts must match. 3. Create two hash maps.

The first map stores character-to-word relationships.

The second map stores word-to-character relationships.

Two maps are necessary because the bijection requirement works in both directions. 4. Iterate through the pattern and words simultaneously.

At each index:

  • Let char be the current pattern character.
  • Let word be the current word.
  1. Check the character-to-word mapping.

If char already exists in the map:

  • Its stored word must equal the current word.

Otherwise:

  • Add the new mapping.
  1. Check the word-to-character mapping.

If word already exists in the map:

  • Its stored character must equal the current character.

Otherwise:

  • Add the new mapping.
  1. If any inconsistency is found, return False immediately.

There is no need to continue because a bijection has already been violated. 8. If the entire iteration completes successfully, return True.

All mappings are consistent and unique.

Why it works

The algorithm maintains an invariant throughout execution:

  • Every processed pattern character maps to exactly one word.
  • Every processed word maps to exactly one pattern character.

Because both directions are checked at every step, no invalid mapping can survive. If the algorithm finishes without detecting a conflict, the mapping is guaranteed to be a valid bijection.

Python Solution

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()

        if len(pattern) != len(words):
            return False

        char_to_word = {}
        word_to_char = {}

        for char, word in zip(pattern, words):
            if char in char_to_word:
                if char_to_word[char] != word:
                    return False
            else:
                char_to_word[char] = word

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

        return True

The implementation begins by splitting the string into words using split(). This produces a list where each word can be matched directly with a pattern character.

The length comparison is an important early exit condition. If the counts differ, there is no valid one-to-one correspondence.

Two dictionaries are then created:

  • char_to_word tracks mappings from pattern characters to words.
  • word_to_char tracks mappings from words back to characters.

The loop processes both sequences simultaneously using zip().

For every pair:

  • If the character already exists in the dictionary, we verify that it maps to the current word.
  • If not, we create the mapping.

The same process is repeated in reverse for the word-to-character mapping.

If any mismatch occurs, the function immediately returns False.

If the loop completes successfully, all mappings satisfy the bijection property, so the function returns True.

Go Solution

func wordPattern(pattern string, s string) bool {
    words := strings.Split(s, " ")

    if len(pattern) != len(words) {
        return false
    }

    charToWord := make(map[byte]string)
    wordToChar := make(map[string]byte)

    for i := 0; i < len(pattern); i++ {
        char := pattern[i]
        word := words[i]

        if mappedWord, exists := charToWord[char]; exists {
            if mappedWord != word {
                return false
            }
        } else {
            charToWord[char] = word
        }

        if mappedChar, exists := wordToChar[word]; exists {
            if mappedChar != char {
                return false
            }
        } else {
            wordToChar[word] = char
        }
    }

    return true
}

The Go solution follows the same logic as the Python version but uses Go maps instead of dictionaries.

One notable difference is that pattern characters are accessed as byte values because the input only contains lowercase English letters. This avoids unnecessary rune handling.

The string is split using strings.Split(s, " "), producing a slice of words.

Go map lookups return both the stored value and a boolean indicating whether the key exists. This is used to distinguish between existing mappings and new ones.

No special handling for nil values or integer overflow is required because the problem constraints are small and the data structures are straightforward.

Worked Examples

Example 1

Input:

pattern = "abba"
s = "dog cat cat dog"

After splitting:

words = ["dog", "cat", "cat", "dog"]
Index Pattern Char Word char_to_word word_to_char Result
0 a dog {a: dog} {dog: a} valid
1 b cat {a: dog, b: cat} {dog: a, cat: b} valid
2 b cat unchanged unchanged valid
3 a dog unchanged unchanged valid

No conflicts occur, so the answer is true.

Example 2

Input:

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

After splitting:

words = ["dog", "cat", "cat", "fish"]
Index Pattern Char Word Observation
0 a dog new mapping
1 b cat new mapping
2 b cat consistent
3 a fish conflict, a already maps to dog

The algorithm returns false.

Example 3

Input:

pattern = "aaaa"
s = "dog cat cat dog"

After splitting:

words = ["dog", "cat", "cat", "dog"]
Index Pattern Char Word Observation
0 a dog new mapping
1 a cat conflict, a already maps to dog

The algorithm immediately returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character-word pair is processed once
Space O(n) Hash maps may store up to n unique mappings

The algorithm performs a single pass through the pattern and word list. Each hash map operation runs in average constant time, so the total runtime is linear.

The space usage is also linear because, in the worst case, every character and every word is unique and must be stored in the maps.

Test Cases

solution = Solution()

assert solution.wordPattern("abba", "dog cat cat dog") == True
# standard valid bijection

assert solution.wordPattern("abba", "dog cat cat fish") == False
# character maps inconsistently

assert solution.wordPattern("aaaa", "dog cat cat dog") == False
# one character maps to multiple words

assert solution.wordPattern("abba", "dog dog dog dog") == False
# multiple characters map to same word

assert solution.wordPattern("abc", "dog cat fish") == True
# all unique mappings

assert solution.wordPattern("abc", "dog cat dog") == False
# word reused by different characters

assert solution.wordPattern("a", "dog") == True
# smallest valid input

assert solution.wordPattern("ab", "dog") == False
# fewer words than pattern characters

assert solution.wordPattern("a", "dog cat") == False
# more words than pattern characters

assert solution.wordPattern("xyzx", "one two three one") == True
# repeated mapping remains consistent

assert solution.wordPattern("xyzx", "one two three four") == False
# repeated character maps differently
Test Why
"abba", "dog cat cat dog" Standard successful case
"abba", "dog cat cat fish" Detects inconsistent mapping
"aaaa", "dog cat cat dog" One character maps to multiple words
"abba", "dog dog dog dog" Two characters map to same word
"abc", "dog cat fish" All mappings unique
"abc", "dog cat dog" Reverse bijection violation
"a", "dog" Minimum valid input
"ab", "dog" Word count mismatch
"a", "dog cat" Extra words present
"xyzx", "one two three one" Valid repeated mapping
"xyzx", "one two three four" Invalid repeated mapping

Edge Cases

One important edge case occurs when the number of words differs from the number of pattern characters. A naive implementation might begin building mappings before checking lengths, leading to incorrect results or index errors. The implementation avoids this by performing an immediate length comparison before processing any mappings.

Another critical edge case is when two different pattern characters attempt to map to the same word. For example, "ab" and "dog dog" should return false. A solution using only one hash map from character to word would incorrectly accept this case. The reverse map from word to character prevents this issue.

A third edge case involves repeated characters mapping inconsistently. For example, "aaaa" with "dog cat cat dog" should fail because the same character cannot map to multiple words. The implementation checks existing mappings every time a character reappears, ensuring consistency throughout the iteration.

A subtle edge case is the smallest possible valid input, such as "a" and "dog". The algorithm handles this naturally because the maps simply store one valid mapping and complete successfully.

Finally, inputs with all unique characters and all unique words must still satisfy bijection rules. Cases like "abc" and "dog cat fish" validate that the implementation correctly handles fully distinct mappings without relying on repeated patterns.