How do you solve Word Pattern on LeetCode?

Word Pattern (LeetCode #290) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: A bijection means each character must map to a unique word and vice versa.

What is the brute force solution for Word Pattern?

The brute force approach for Word Pattern is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we try to create a mapping between characters in the pattern and words in the string. We check all possible combinations to see if they fit the bijection requirement, which can be quite slow. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Word Pattern?

Word Pattern uses the following concepts: Hash Table, String. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Word Pattern?

Always check for edge cases, like different lengths of pattern and words. Explain your thought process clearly while coding; it helps the interviewer understand your approach. Use meaningful variable names to improve code readability.

What are common mistakes when solving Word Pattern?

Failing to check the length of the pattern and the words array before mapping. Not considering the case where a character or word already exists in the mapping.

#290

Word Pattern

Easy

Hash TableStringHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

This approach uses two hash maps to create a one-to-one mapping between characters and words efficiently, ensuring we only traverse the input once.

⚙️

Algorithm

3 steps

1Step 1: Split the string 's' into words.
2Step 2: Initialize two hash maps: one for character to word mapping and another for word to character mapping.
3Step 3: Iterate through the pattern and words simultaneously, updating the hash maps and checking for consistency.

solution.py20 lines

1# Full working Python code
2
3def wordPattern(pattern, s):
4    words = s.split()
5    if len(pattern) != len(words):
6        return False
7    char_to_word = {}
8    word_to_char = {}
9    for char, word in zip(pattern, words):
10        if char in char_to_word:
11            if char_to_word[char] != word:
12                return False
13        else:
14            char_to_word[char] = word
15        if word in word_to_char:
16            if word_to_char[word] != char:
17                return False
18        else:
19            word_to_char[word] = char
20    return True

ℹ

Complexity note: The time complexity is O(n) because we only traverse the pattern and the words once, making it efficient. The space complexity is O(n) due to the storage of mappings in hash maps.

1A bijection means each character must map to a unique word and vice versa.
2The number of unique characters must match the number of unique words.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.