| 链接 | 单词规律 |
|---|---|
| 题序号 | 290 |
| 题型 | 字符串 |
| 解题方法 | 哈希表 |
| 难度 | 简单 |
| 熟练度 | ✅✅✅ |
题目
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = “abba”, s = “dog cat cat dog”
输出: true示例 2:
输入:pattern = “abba”, s = “dog cat cat fish”
输出: false示例 3:
输入: pattern = “aaaa”, s = “dog cat cat dog”
输出: false提示:
1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ’ ’
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔
题解
-
核心要点：
- 使用两个哈希表来存储 pattern 中的字符到 s 中的单词的映射关系，以及 s 中的单词到 pattern 中的字符的映射关系。
- 遍历 pattern 和 s，检查每个字符和单词的映射关系是否一致。
- 如果在遍历过程中发现映射关系不一致，则返回 false。
- 如果遍历结束后没有发现不一致的映射关系，则返回 true。
-
复杂度：时间复杂度和空间复杂度都是O(n+m)。
-
c++ 实现算法：
bool wordPattern(string pattern, string s) {unordered_map<char, string> charToWord; // 保存 pattern 中字符到单词的映射unordered_map<string, char> wordToChar; // 保存单词到 pattern 中字符的映射istringstream ss(s); // 将字符串 s 转换为输入流string word;int i = 0;//ss>>word 从字符串流中读取一个单词放到 wordwhile (ss >> word) {if (i >= pattern.size()) return false; // 单词数量多于 pattern 字符数量char c = pattern[i]; //从 pattern 中取出当前索引 i 对应的字符，赋值给变量 c// 检查 pattern->word 的映射if (charToWord.count(c)) { // 如果当前 pattern 字符已经有映射if (charToWord[c] != word) return false; // 如果映射不一致，返回 false} else {charToWord[c] = word; //如果不存在映射，则将当前单词和字符添加到 wordToChar 中}// 检查 word->pattern 的映射，过程同理if (wordToChar.count(word)) {if (wordToChar[word] != c) return false;} else {wordToChar[word] = c;}i++;}return i == pattern.size(); // 确保没有多余的模式字符
}
- 推演算法：
示例 1
输入：
pattern = “abba” s = “dog cat cat dog”执行过程：
第一次迭代：
当前单词：“dog”
当前字符：‘a’
wordToChar.count(“dog”) = 0（单词未映射）
添加映射：wordToChar[“dog”] = ‘a’
第二次迭代：
当前单词：“cat”
当前字符：‘b’
wordToChar.count(“cat”) = 0（单词未映射）
添加映射：wordToChar[“cat”] = ‘b’
第三次迭代：
当前单词：“cat”
当前字符：‘b’
wordToChar.count(“cat”) = 1（单词已映射）
检查映射：wordToChar[“cat”] == ‘b’，映射一致，继续。
第四次迭代：
当前单词：“dog”
当前字符：‘a’
wordToChar.count(“dog”) = 1（单词已映射）
检查映射：wordToChar[“dog”] == ‘a’，映射一致，继续。结果： 映射通过，返回 true。
示例 2
输入：
pattern = “abba” s = “dog cat cat fish”步骤 1：
初始化 charToWord = {} wordToChar = {} istringstream 分割 s 为单词流 [“dog”, “cat”, “cat”, “fish”]。
i = 0步骤 2：
遍历模式和单词
第 1 次迭代 当前模式字符：‘a’ 当前单词：“dog” 建立映射： ‘a’ -> “dog” “dog” -> ‘a’
第 2 次迭代 当前模式字符：‘b’ 当前单词：“cat” 建立映射： ‘b’ -> “cat” “cat” -> ‘b’
第 3 次迭代 当前模式字符：‘b’ 当前单词：“cat” 检查映射： ‘b’ 映射为 “cat”，一致。 “cat” 映射为
‘b’，一致。
第 4 次迭代 当前模式字符：‘a’ 当前单词：“fish” 检查映射： ‘a’ 映射为 “dog”，但当前单词是 “fish” →
不一致。步骤 3：
返回结果 映射不一致，返回 false。
- c++ 完整demo：
#include <iostream>
#include <unordered_map>
#include <sstream>
using namespace std;bool wordPattern(string pattern, string s) {unordered_map<char, string> charToWord; // 保存 pattern 中字符到单词的映射unordered_map<string, char> wordToChar; // 保存单词到 pattern 中字符的映射istringstream ss(s); // 将字符串 s 转换为输入流string word;int i = 0;//ss>>word 从字符串流中读取一个单词放到 wordwhile (ss >> word) {if (i >= pattern.size()) return false; // 单词数量多于 pattern 字符数量char c = pattern[i]; //从 pattern 中取出当前索引 i 对应的字符，赋值给变量 c// 检查 pattern->word 的映射if (charToWord.count(c)) { // 如果当前 pattern 字符已经有映射if (charToWord[c] != word) return false; // 如果映射不一致，返回 false} else {charToWord[c] = word; //如果不存在映射，则将当前单词和字符添加到 wordToChar 中}// 检查 word->pattern 的映射，过程同理if (wordToChar.count(word)) {if (wordToChar[word] != c) return false;} else {wordToChar[word] = c;}i++;}return i == pattern.size(); // 确保没有多余的模式字符
}int main() {string pattern = "abba";string s = "dog cat cat dog";if (wordPattern(pattern, s)) {cout << "True" << endl;} else {cout << "False" << endl;}return 0;
}
