LC290. 单词规律

题目描述

给定一种规律 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. 一个模式串 `pattern`：它是一个由小写字母组成的字符串，比如 "abba"。你可以把它想象成一种“密码”，里面的每个字母（比如 'a'、'b'）就是一个“代号”。 2. 一个句子 `s`：它是由空格隔开的几个单词组成的，比如 "dog cat cat dog"。

题目的要求是：判断这个句子里的单词，能不能完美地匹配上这个模式里的代号。

怎么才算“完美匹配”呢？需要满足两个条件：

• 条件一（从代号到单词）：模式里的同一个代号，必须对应句子里同一个单词。比如，模式里所有的 'a'，都必须对应同一个单词。
• 条件二（从单词到代号）：反过来，句子里同一个单词，也必须对应模式里同一个代号。比如，句子里所有的 "dog"，都必须对应同一个代号。

这两个条件必须同时成立，缺一不可。这就是所谓的“双向连接”。

我们来看几个例子，你就明白了：

• 示例1： pattern = "abba", s = "dog cat cat dog"
• 第一个 'a' 对应 "dog"，最后一个 'a' 也对应 "dog"。✅ 条件一满足。
• 第一个 "dog" 对应 'a'，最后一个 "dog" 也对应 'a'。✅ 条件二满足。
• 中间的 'b' 和 "cat" 也是互相唯一对应。
• 所以结果是 `true`。

• 示例2： pattern = "abba", s = "dog cat cat fish"
• 第一个 'a' 对应 "dog"，最后一个 'a' 却对应 "fish"。同一个代号 'a' 对应了两个不同的单词。❌ 条件一被破坏。
• 所以结果是 `false`。

• 示例3： pattern = "aaaa", s = "dog cat cat dog"
• 第一个 'a' 对应 "dog"，第二个 'a' 却对应 "cat"。同一个代号 'a' 对应了两个不同的单词。❌ 条件一被破坏。
• 所以结果是 `false`。

总结一下：我们就是要检查，代号和单词之间，是不是一个“萝卜一个坑”，互相之间都是一对一的，不能出现“多对一”或“一对多”的情况。

---

### 思路是怎么来的

想象一下，你是一个班级的班主任，手里有两张名单：

1. 代号名单（pattern）：上面写着每个学生的“学号”，比如 ['a', 'b', 'b', 'a']。 2. 名字名单（s）：上面写着每个学生的“姓名”，比如 ['dog', 'cat', 'cat', 'dog']。

现在，你要检查这两张名单是不是“对得上”。也就是说，学号 'a' 是不是永远都叫 "dog"，学号 'b' 是不是永远都叫 "cat"，反过来也一样。

你会怎么做？最直接的办法就是：

拿两张空白的“对照表”出来。

• 第一张表（dic1）：用来记录“名字 → 学号”的对应关系。比如，你看到第一个学生叫 "dog"，学号是 'a'，你就在这张表上写："dog" 对应 'a'。
• 第二张表（dic2）：用来记录“学号 → 名字”的对应关系。比如，你看到第一个学生学号是 'a'，名字叫 "dog"，你就在这张表上写：'a' 对应 "dog"。

然后，你开始一个一个地检查学生：

1. 检查第一个学生：名字 "dog"，学号 'a'。

• 查第一张表："dog" 还没出现过，好，记上 "dog" -> 'a'。
• 查第二张表：'a' 还没出现过，好，记上 'a' -> "dog"。
• 一切正常，继续。

2. 检查第二个学生：名字 "cat"，学号 'b'。

• 查第一张表："cat" 还没出现过，记上 "cat" -> 'b'。
• 查第二张表：'b' 还没出现过，记上 'b' -> "cat"。
• 一切正常，继续。

3. 检查第三个学生：名字 "cat"，学号 'b'。

• 查第一张表："cat" 已经出现过，它对应的学号是 'b'。而当前这个学生的学号也是 'b'。✅ 对得上！