双哈希

我们用两个哈希表。一个维护pattern的字母和单词的映射，另外一个维护单词和pattern的字母的映射。

模拟匹配即可。

时间复杂度$O(N)$，空间复杂度$O(N)$

AC代码

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        vector<string> words;
        int n = s.size(), m = pattern.size();
        for (int i = 0 ; i < n ; i ++) {
            if (s[i] == ' ') continue;
            string t;int j = i;
            while (j < n && s[j] != ' ') t += s[j ++];
            i = j;
            words.push_back(t);
        }
        n = words.size();
        if (n != m) return false;
        unordered_map<char, string> ps;
        unordered_map<string, char> sp;
        for (int i = 0 ; i < m ; i ++) {
            char c = pattern[i];
            if (ps.count(c) && ps[c] != words[i]) 
                return false;
            ps[c] = words[i];
            if (sp.count(words[i]) && sp[words[i]] != c)
                return false;
            sp[words[i]] = c;
        }
        return true;
    }
};