题目描述

给定一种规律 pattern 和一个字符串 str ，判断 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

说明

你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。

算法

(哈希表) $O(n)$

本题与 LeetCode 205. Isomorphic Strings 类似，题意是让我们判断两个字符串的每个位置能否构成一一对应关系，即能否构成双射 (Bijection)。双射是指既是单射 (Injection) 又是满射 (Surjection) 的映射。这里单射的形式化定义如下：

函数 $f: A \to B$ 是单射，当且仅当对于所有 $a,b \in A$, 我们有 $f(a) = f(b) \Rightarrow a = b$。换句话说单射就是把相同的值映射到相同的像上，把不同的值映射到不同的像上，每一个值对应唯一的像而且每一个对应的像都对应唯一的值，但是 $B$ 中可以有像没有值与它对应。

那么如果 $A \to B$ 是单射并且 $A,B$ 的大小相同，则 $A,B$ 之间就是双射，或者叫一一映射。我们用一个哈希表可以存储不同的值key对像value的映射，但是因为哈希表是单向的即只能检索值key不能检索像value，所以不同的值依然有可能会映射到相同的像上。我们需要另外开一个哈希表来存储像到值的映射，即value到key的映射。这样我们就可以保证像和值是一一对应的，当我们把 $A$ 中的每一个元素都找到一一对应后，由于大小相同，我们就构成了双射。

注意对这道题而言只满足数学意义上的双射是不行的，因为数学意义上的集合是无序且无重复的。而这里字符串是有顺序且会有重复的，所以我们需要从头到尾扫描一遍字符串，每当遇到一个还没找到一一对应元素的字符，我们就将它对应位置的字符串当做它的像，即按顺序满足一一对应的要求。

另外由于C++中的string并没有split方法，我们这里可以用stringstream来将str分割成string数组。

参考文献

单射、双射与满射

C++ 代码

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        stringstream ss(str);
        vector<string> words;
        string word;
        while (ss >> word) words.push_back(word);
        if (words.size() != pattern.size()) return false;

        unordered_map<string, char> SP;
        unordered_map<char, string> PS;
        for (int i = 0; i < words.size(); i ++ ) {
            if (SP.count(words[i]) || PS.count(pattern[i])) {
                if (SP[words[i]] != pattern[i] || PS[pattern[i]] != words[i]) 
                    return false;
            } else {
                SP[words[i]] = pattern[i];
                PS[pattern[i]] = words[i];
            }
        }
        return true;
    }
};