Code Implementation

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 c, w in zip(pattern, words):
            if c in char_to_word:
                if char_to_word[c] != w:
                    return False
            else:
                char_to_word[c] = w
            if w in word_to_char:
                if word_to_char[w] != c:
                    return False
            else:
                word_to_char[w] = c
        return True
      

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        istringstream iss(s);
        string word;
        while (iss >> word) words.push_back(word);

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

        unordered_map<char, string> char_to_word;
        unordered_map<string, char> word_to_char;

        for (int i = 0; i < pattern.length(); ++i) {
            char c = pattern[i];
            string w = words[i];
            if (char_to_word.count(c)) {
                if (char_to_word[c] != w) return false;
            } else {
                char_to_word[c] = w;
            }
            if (word_to_char.count(w)) {
                if (word_to_char[w] != c) return false;
            } else {
                word_to_char[w] = c;
            }
        }
        return true;
    }
};
      

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

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

        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String w = words[i];
            if (charToWord.containsKey(c)) {
                if (!charToWord.get(c).equals(w)) return false;
            } else {
                charToWord.put(c, w);
            }
            if (wordToChar.containsKey(w)) {
                if (wordToChar.get(w) != c) return false;
            } else {
                wordToChar.put(w, c);
            }
        }
        return true;
    }
}
      

var wordPattern = function(pattern, s) {
    const words = s.split(' ');
    if (pattern.length !== words.length) return false;

    const charToWord = {};
    const wordToChar = {};

    for (let i = 0; i < pattern.length; ++i) {
        const c = pattern[i];
        const w = words[i];
        if (charToWord[c]) {
            if (charToWord[c] !== w) return false;
        } else {
            charToWord[c] = w;
        }
        if (wordToChar[w]) {
            if (wordToChar[w] !== c) return false;
        } else {
            wordToChar[w] = c;
        }
    }
    return true;
};
      

Problem Description

You are given a string pattern consisting of lowercase English letters and a string s consisting of words separated by spaces. Your task is to determine if s follows the same pattern as pattern.

Specifically, there must be a one-to-one correspondence (bijection) between each character in pattern and each word in s:

• Each character in pattern maps to exactly one word in s.
• No two different characters map to the same word, and no two different words map to the same character.

Constraints:

• Each word in s is non-empty and separated by a single space.
• The number of characters in pattern must match the number of words in s for a valid mapping.
• Each mapping must be unique and consistent; elements cannot be reused.

Thought Process

At first glance, the problem resembles checking if two sequences follow the same structure, similar to checking if two strings are isomorphic. A brute-force approach might involve comparing every possible mapping, but this quickly becomes inefficient and complex, especially as the input size grows.

The key insight is that we need to ensure that each character in pattern consistently maps to the same word in s, and vice versa. If we find any inconsistency, the pattern does not match.

To do this efficiently, we can use two hash maps (or dictionaries): one to map pattern characters to words, and another to map words back to pattern characters. This dual mapping ensures that the correspondence is truly one-to-one and prevents accidental reuse.

The optimized approach avoids unnecessary comparisons and leverages the constant-time lookup of hash maps to check for mapping validity as we iterate through the pattern and the words.

Solution Approach

To solve the problem efficiently, we use the following step-by-step method:

1. Split the string s into words: Use the space character to break s into a list of words.
2. Check length equality: If the number of characters in pattern does not match the number of words in s, return False immediately. This is a necessary condition for a valid bijection.
3. Initialize two hash maps:
   • One map (char_to_word) from pattern characters to words.
   • Another map (word_to_char) from words back to pattern characters.
4. Iterate through the pattern and words together: For each character and corresponding word:
   • If the character has been seen before, check if it maps to the current word. If not, return False.
   • If the word has been seen before, check if it maps to the current character. If not, return False.
   • If neither has been seen before, add the mapping in both hash maps.
5. If all pairs are consistent, return True: This means the string s follows the given pattern.

Using hash maps ensures that both forward and backward mappings are unique and consistent, guaranteeing the bijection required by the problem.

Example Walkthrough

Let's consider pattern = "abba" and s = "dog cat cat dog".

1. Split s into ["dog", "cat", "cat", "dog"].
2. Both pattern and the word list have length 4, so we continue.
3. Initialize empty maps: char_to_word = {}, word_to_char = {}.
4. Iterate through each pair:
   • First pair: 'a' → "dog"
     • 'a' not in char_to_word, "dog" not in word_to_char. Add mappings: char_to_word['a'] = "dog", word_to_char["dog"] = 'a'.
   • Second pair: 'b' → "cat"
     • 'b' not in char_to_word, "cat" not in word_to_char. Add mappings: char_to_word['b'] = "cat", word_to_char["cat"] = 'b'.
   • Third pair: 'b' → "cat"
     • 'b' in char_to_word maps to "cat", which matches the current word. Continue.
     • "cat" in word_to_char maps to 'b', which matches the current character. Continue.
   • Fourth pair: 'a' → "dog"
     • 'a' in char_to_word maps to "dog", which matches the current word. Continue.
     • "dog" in word_to_char maps to 'a', which matches the current character. Continue.
5. All pairs consistent. Return True.

If at any step a mapping did not match, we would immediately return False.

Time and Space Complexity

Brute-force approach: Trying every possible mapping between pattern characters and words would have factorial time complexity, which is infeasible for even moderately sized inputs.

Optimized approach (using hash maps):

• Time Complexity: O(n), where n is the length of the pattern (or the number of words). We process each character and corresponding word exactly once, and hash map operations are on average constant time.
• Space Complexity: O(n) in the worst case, due to the storage of mappings in the hash maps.

Summary

The Word Pattern problem is elegantly solved by leveraging two hash maps to enforce a one-to-one correspondence between pattern characters and words. By checking both forward and backward mappings, the solution ensures consistency and uniqueness throughout the sequences. This approach is efficient, easy to understand, and avoids the pitfalls of brute-force mapping, making it a great example of how hash maps can simplify bijection problems.