Word Pattern – 290. LeetCode

The “Word Pattern” problem involves checking if a given pattern string matches a sequence of words. Each character in the pattern corresponds to a word in the sequence, and the mapping between them must be consistent: no two characters can map to the same word, and no character can map to multiple words. For example, given pattern = “abba” and s = “dog cat cat dog”, the function should return true because the character-word mapping is consistent.

Brute Force Approach

public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) return false;

    for (int i = 0; i < pattern.length(); i++) {
        for (int j = i + 1; j < pattern.length(); j++) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                if (!words[i].equals(words[j])) return false;
            } else {
                if (words[i].equals(words[j])) return false;
            }
        }
    }
    return true;
}

This code split the input string s into an array of words. It checks all pairs of indices to ensure that:

• If two characters in the pattern are the same, their corresponding words are the same.
• If two characters in the pattern are different, their corresponding words are different.

Optimal Solution: Hash Maps for Bidirectional Mapping

Algorithmic and Data Structure Pattern

• Pattern: Hash Maps for mapping relationships.

• Data Structure: Two hash maps to track forward and reverse mappings between characters and words.

A bidirectional hash map uses two separate hash maps to maintain two-way mappings between keys and values.

These two maps ensure that:

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

This bidirectional mapping prevents conflicts that could arise if one direction of mapping were ambiguous.

Steps of the Algorithm

1. Split the string s into an array of words.

2. Check if the length of pattern matches the length of the words array.

3. Create two hash maps: one for pattern-to-word mapping and one for word-to-pattern mapping.

4. For each character in the pattern:

• Check consistency in both mappings.

5. Return true if mappings are consistent; otherwise, false.

import java.util.HashMap;

public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) return false;

    HashMap<Character, String> charToWord = new HashMap<>();
    HashMap<String, Character> wordToChar = new HashMap<>();

    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        String word = words[i];

        // Check consistency of pattern-to-word mapping
        if (charToWord.containsKey(c)) {
            if (!charToWord.get(c).equals(word)) return false;
        } else {
            charToWord.put(c, word);
        }

        // Check consistency of word-to-pattern mapping
        if (wordToChar.containsKey(word)) {
            if (!wordToChar.get(word).equals(c)) return false;
        } else {
            wordToChar.put(word, c);
        }
    }

    return true;
}

Line By Line Explanation

Step 1: Split the input string into words

String[] words = s.split(" ");

• Splits the string s into an array of words, using spaces as the delimiter. For example, “dog cat cat dog” becomes [“dog”, “cat”, “cat”, “dog”].
• This preprocessing step is efficient and easy to understand, ensuring that s is converted into a format suitable for comparison.

Step 2: Check if lengths match

if (pattern.length() != words.length) return false;

• This avoids unnecessary computation later, adhering to the principle of “failing fast”.

Step 3: Initialize hash maps for bidirectional mapping

HashMap<Character, String> charToWord = new HashMap<>();
HashMap<String, Character> wordToChar = new HashMap<>();

• A one-to-one mapping requires noth directions:
  • Ensure each character maps to a unique word.
  • Ensure each word maps to a unique character.
• Hashmaps provide constant-time lookups.

Step 4: Iterate through the pattern and words

for (int i = 0; i < pattern.length(); i++) {
    char c = pattern.charAt(i);
    String word = words[i];

• Loops through each character in the pattern and its corresponding word in words.
• Allows pairwise comparison between characters and words to validate the mapping.

Step 5: Check and update pattern-to-word mapping

if (charToWord.containsKey(c)) {
    if (!charToWord.get(c).equals(word)) return false;
} else {
    charToWord.put(c, word);
}

• If c is already mapped to a word, verify that it maps to the same word.
• If c is not mapped, add the mapping c -> word to the hash map.

Step 6: Check and update word-to-pattern mapping

if (wordToChar.containsKey(word)) {
    if (!wordToChar.get(word).equals(c)) return false;
} else {
    wordToChar.put(word, c);
}

• If word s already mapped to a character, verify that it maps to the same character.
• If word is not mapped, add the mapping word -> c to the hash map.
• This directional check prevents conflicts, ensuring correctness with minimal extra space usage.

Step 7: Return

return true;

• Cleanly handles the result of the validation checks, adhering to clarity and correctness.

Why This Code Works

1. Efficiency

• The code uses O(n) time complexity due to single-pass iteration and hash map operations, which are optimal for this problem.

2. Readability:

• The logic is broken into clear, logical steps, making it easy to follow and debug.

3. Scalability:

• The code efficiently handles larger inputs because of the hash maps’ constant-time operations.

4. Prevention of Edge Case Failures:

• Length check and bidirectional mapping handle common edge cases, such as mismatched lengths or conflicting mappings.

Summary

This code adheres to LeetCode best practices by being efficient, scalable, and clear, ensuring correctness while maintaining a clean and concise implementation. Each part of the code is purpose-driven, leveraging hash maps to handle mappings in a way that minimizes time and space complexity.