题目描述

给定一个模式串pattern和一个句子str，请判断句子str是否具有pattern的模式。即判断pattern中的字母和str中的 非空 单词是否存在双射关系。

注意： pattern中只包含小写字母，str中只包含小写字母和空格。

样例1

输入：pattern = "abba", str = "dog cat cat dog"
输出：true

样例2

输入：pattern = "abba", str = "dog cat cat fish"
输出：false

样例3

输入：pattern = "aaaa", str = "dog cat cat dog"
输出：false

样例4

输入：pattern = "abba", str = "dog dog dog dog"
输出：false

算法

(哈希表) $O(L)$

此题与LeetCode 205. Isomorphic Strings类似。

假设pattern有 $n$ 个字母，str有 $n$ 个单词。相当于给了我们 $n$ 组字母和单词的对应关系，然后问字母和单词是否一一对应，即相同字母对应相同单词，且不同字母对应不同单词。
不同字母对应不同单词，等价于相同单词对应相同字母。

所以我们可以用两个哈希表，分别存储单词对应的字母，以及字母对应的单词。
然后从前往后扫描，判断相同元素对应的值，是否是相同的。

时间复杂度分析：数组和单词仅被遍历一次，所以时间复杂度是线性的。假设str的长度是 $L$，那么总时间复杂度就是 $O(L)$。

C++ 代码

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        stringstream raw(str);
        vector<string> strs;
        string line;
        while (raw >> line) strs.push_back(line);
        if (pattern.size() != strs.size()) return false;
        unordered_map<char, string> PS;
        unordered_map<string, char> SP;
        for (int i = 0; i < pattern.size(); i ++ )
        {
            if (PS.count(pattern[i]) == 0) PS[pattern[i]] = strs[i];
            if (SP.count(strs[i]) == 0) SP[strs[i]] = pattern[i];
            if (PS[pattern[i]] != strs[i]) return false;
            if (SP[strs[i]] != pattern[i]) return false;
        }
        return true;
    }
};