今天和大家聊的问题叫做 单词规律，我们先来看题面：https://leetcode-cn.com/problems/word-pattern/
Given a pattern and a string s, find if s 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 s.
给定一种规律 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 包含了由单个空格分隔的小写字母。
解题
方法一：哈希表
在本题中，我们需要判断字符与字符串之间是否恰好一一对应。即任意一个字符都对应着唯一的字符串，任意一个字符串也只被唯一的一个字符对应。在集合论中，这种关系被称为「双射」。
想要解决本题，我们可以利用哈希表记录每一个字符对应的字符串，以及每一个字符串对应的字符。然后我们枚举每一对字符与字符串的配对过程，不断更新哈希表，如果发生了冲突，则说明给定的输入不满足双射关系。
在实际代码中，我们枚举pattern 中的每一个字符，利用双指针来均摊线性地找到该字符在 str 中对应的字符串。每次确定一个字符与字符串的组合，我们就检查是否出现冲突，最后我们再检查两字符串是否比较完毕即可。
class Solution { public: bool wordPattern(string pattern, string str) { unordered_map<string, char> str2ch; unordered_map<char, string> ch2str; int m = str.length(); int i = 0; for (auto ch : pattern) { if (i >= m) { return false; } int j = i; while (j < m && str[j] != ' ') j++; const string &tmp = str.substr(i, j - i); if (str2ch.count(tmp) && str2ch[tmp] != ch) { return false; } if (ch2str.count(ch) && ch2str[ch] != tmp) { return false; } str2ch[tmp] = ch; ch2str[ch] = tmp; i = j + 1; } return i >= m; } };
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
