word-pattern.cpp

// Time:  O(n)
// Space: O(c), c is unique count of pattern

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        // Count the words.
        int cnt = str.empty() ? 0 : 1;
        for (const auto& c : str) {
            if (c == ' ') {
                ++cnt;
            }
        }
        if (pattern.size() != cnt) {
            return false;
        }

        unordered_map<string, char> w2p;
        unordered_map<char, string> p2w;
        int i = 0, j = 0;
        for (const auto& p : pattern) {
            // Get a word at a time without saving all the words.
            j = str.find(" ", i);
            if (j == string::npos) {
                j = str.length();
            }
            const string w = str.substr(i, j - i);
    
            if (!w2p.count(w) && !p2w.count(p)) { 
                // Build mapping. Space: O(c)
                w2p[w] = p; 
                p2w[p] = w; 
            } else if (!w2p.count(w) || w2p[w] != p) {
                // Contradict mapping.
                return false;
            }
            i = j + 1;
        }
        return true;
    }
};