Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat cat dog" should return false. pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution: Using two hash tables

The key is to use two hash tables to check if the words are following the pattern.

bool wordPattern(string pattern, string str) {
    unordered_map<char, string> patternToWord;
    unordered_map<string, char> wordToPatter;
    str += " "; // add space for finding

    for (auto p : pattern) {
        if (str.empty()) return false;

        // Find word
        auto pos = str.find(' ');
        string word = str.substr(0, pos);
        str = str.substr(pos + 1);

        // If pattern found in map, but word is not equal to 
        if (patternToWord.count(p) && patternToWord[p] != word) return false;
        if (wordToPatter.count(word) && wordToPatter[word] != p) return false;

        // Update map
        patternToWord[p] = word;
        wordToPatter[word] = p;
    }

    if (str.size() > 0) {
        return false;
    }

    return true;
}