当前位置：首页 > news >正文

Leetcode 每日一题 290.单词规律

news 来源：原创 2025/5/13 22:25:21

一、问题分析

二、解题思路

三、代码实现

四、复杂度分析

五、总结

在编程的世界里，我们常常会遇到各种有趣的字符串匹配问题。今天要探讨的就是这样一个问题：给定一种规律 pattern 和一个字符串 s，判断 s 是否遵循与 pattern 相同的规律。这里的 “遵循” 意味着 pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

一、问题分析

首先，我们明确一下问题的关键要求：

pattern 仅包含小写英文字母，其长度范围是 1 <= pattern.length <= 300。
s 包含小写英文字母和空格，且不包含前导或尾随空格，每个单词由单个空格分隔，长度范围是 1 <= s.length <= 3000。
pattern 与 s 之间的对应关系必须是双向的，即一个字母对应一个特定单词，且一个单词也只能对应一个特定字母。

二、解题思路

为了判断这种双向对应关系，我们可以利用两个哈希表来分别记录从 pattern 中的字符到 s 中的单词的映射，以及从 s 中的单词到 pattern 中的字符的映射。

首先，将字符串 s 按照空格进行分割，得到一个单词数组 ss。如果 pattern 的长度与 ss 的长度不相等，那么直接返回 false，因为它们不可能存在一一对应的关系。
然后，遍历 pattern 和 ss，对于每一个位置 i：
- 将 pattern 中的字符作为键，ss 中的单词作为值存入 map 哈希表。
- 将 ss 中的单词作为键，pattern 中的字符作为值存入 map1 哈希表。
最后，再次遍历 pattern 和 ss，检查 map 和 map1 中的映射关系是否正确。如果在任何位置发现不匹配的情况，即 map 中通过字符获取的单词与实际的 ss[i] 不相等，或者 map1 中通过单词获取的字符与实际的 pattern.charAt(i) 不相等，就返回 false。如果整个遍历过程都没有发现不匹配，那么说明 s 遵循 pattern 的规律，返回 true。

过题图片

三、代码实现

以下是使用 Java 实现的代码：

class Solution {public boolean wordPattern(String pattern, String s) {// 用于存储从 pattern 中的字符到 s 中的单词的映射HashMap<Character,String> map = new HashMap<>();// 用于存储从 s 中的单词到 pattern 中的字符的映射HashMap<String,Character> map1 = new HashMap<>();// 将 s 按照空格分割成单词数组String[] ss = s.split(" ");// 如果 pattern 长度与单词数组长度不相等，直接返回 falseif(pattern.length()!= ss.length) return false;// 遍历 pattern 和单词数组，建立双向映射for(int i = 0; i < pattern.length(); i++){map.put(pattern.charAt(i), ss[i]);map1.put(ss[i], pattern.charAt(i));}// 再次遍历，检查映射关系是否正确for(int i = 0; i < pattern.length(); i++){if(!map.get(pattern.charAt(i)).equals(ss[i])){return false;}if(!map1.get(ss[i]).equals(pattern.charAt(i))){return false;}}return true;}
}

四、复杂度分析

时间复杂度：主要的操作是对 pattern 和 ss 进行两次遍历。第一次遍历用于建立哈希表，时间复杂度为，其中是 pattern 的长度（也是 ss 的长度）。第二次遍历用于检查映射关系，时间复杂度也为。所以总的时间复杂度为。
空间复杂度：需要创建两个哈希表来存储映射关系，在最坏情况下，哈希表中可能存储 pattern 中的所有字符和 ss 中的所有单词，所以空间复杂度为，其中是 pattern 的长度（也是 ss 的长度）。

题目链接

290. 单词规律 - 力扣（LeetCode）

五、总结

题目要求判断字符串 s 与给定的规律 pattern 是否完全匹配，这里的匹配是一种双向连接的对应关系，即 pattern 里的每个字母要和 s 中的每个非空单词一一对应，且反之亦然。同时，题目对 pattern 和 s 的长度、字符组成以及 s 的单词分隔形式等都做了相应限定，明确这些要求是正确解题的基础。

一、问题分析

二、解题思路

三、代码实现

四、复杂度分析

五、总结

相关文章：