290. 单词规律【 力扣(LeetCode) 】

一、题目描述

给定一种规律 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 中每个单词都被 单个空格 分隔

三、解题思路

1. 基本思路：
     建立字符串 s 和 pattern 的双向映射并检查是否冲突
2. 具体思路：
   • 拆分：先将字符串 s 按空格拆分成单词。
   • 建立映射并检查冲突：遍历字符串 pattern，如果不存在 字符串 s 和 pattern 的映射，则建立字符串 s 和 pattern 的双向映射；如果存在，则检查是否冲突。

四、参考代码

时间复杂度：$\mathrm{O}(n+m)$ 【字符串 s 和 pattern 都要遍历一遍】
空间复杂度：$\mathrm{O}(n+m)$ 【最坏情况下要把字符串 s 和 pattern 全部存进 map 中】

class Solution {
public:vector<string> split(string s, char t) {int n = s.length(), i, j;vector<string> ans;for (i = 0, j = 0; j < n; j++) {if (s[j] == t) {ans.push_back(s.substr(i, j - i));i = j + 1;}}ans.push_back(s.substr(i, j - i));return ans;}bool wordPattern(string pattern, string s) {int n = pattern.length();vector<string> str = split(s, ' ');if (str.size() != n)return false;map<char, string> m1;map<string, char> m2;for (int i = 0; i < n; i++) {if (m1.count(pattern[i]) == 1 || m2.count(str[i]) == 1) {if (m1[pattern[i]] != str[i] || m2[str[i]] != pattern[i])return false;} else {m1[pattern[i]] = str[i];m2[str[i]] = pattern[i];}}return true;}
};