Word Pattern

How it works

Using only one hash map from character to index, we can still verify the bijection by iterating through existing mappings when encountering a new character. Since there are at most 26 lowercase letters, this iteration is bounded by a constant. We check if any existing character already maps to the current word, ensuring no two characters share the same word.

Steps

1. Split the string and check that pattern and word counts are equal.
2. Create a single map from characters to their first occurrence index.
3. For each character-word pair, if the character exists in the map, verify the stored index points to the same word.
4. If the character is new, iterate through all existing mappings to ensure no other character maps to this word.
5. If a conflict is found, return false. Otherwise, add the new mapping.
6. Return true after processing all pairs successfully.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(m)

Where n is the length of the string pattern and m is the length of the string s.

Things to watch for

Only Checking One Direction of the Mapping

A common mistake is using only one hash map to check if each pattern character maps to the same word, but forgetting to verify the reverse. This fails cases like pattern = "abba" and s = "dog dog dog dog" where a -> dog and b -> dog would both be stored, incorrectly returning true.

Forgetting to Check Length Mismatch Early

Failing to compare the pattern length with the word count before iterating leads to index errors or incorrect results. For example, pattern = "ab" with s = "dog" has a mismatch that should immediately return false.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(pattern) != len(words):
            return False

        charToWord = {}

        for i, (c, w) in enumerate(zip(pattern, words)):
            if c in charToWord:
                if words[charToWord[c]] != w:
                    return False
            else:
                # iterates atmost 26 times (a - z)
                for k in charToWord:
                    if words[charToWord[k]] == w:
                        return False
                charToWord[c] = i

        return True

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

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

        unordered_map<char, int> charToWord;
        for (int i = 0; i < pattern.size(); ++i) {
            char c = pattern[i];
            const string& w = words[i];

            if (charToWord.count(c)) {
                if (words[charToWord[c]] != w) {
                    return false;
                }
            } else {
                for (const auto& [key, val] : charToWord) {
                    if (words[val] == w) {
                        return false;
                    }
                }
                charToWord[c] = i;
            }
        }

        return true;
    }
};