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

LeetCode题练习与总结：单词规律--290

article 2024/10/9 15:41:27

一、题目描述

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

二、解题思路

首先，我们需要将字符串 s 按照空格分割成单词数组。
然后，我们需要检查两个条件：pattern 的长度是否与单词数组的长度相等。如果不相等，直接返回 false。
接下来，我们需要使用两个哈希表（或HashMap）来记录 pattern 中的字符与 s 中的单词之间的映射关系。
遍历 pattern 和单词数组，分别将字符与对应位置的单词存入哈希表中。
在存储映射关系的同时，我们需要检查：
- 当前字符是否已经映射到了某个单词，如果是，检查是否与当前单词相同，不同则返回 false。
- 当前单词是否已经被映射到了某个字符，如果是，检查是否与当前字符相同，不同则返回 false。
如果遍历结束都没有返回 false，则说明 s 遵循了 pattern 的规律，返回 true。

三、具体代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) {
            return false;
        }
        
        Map<Character, String> charToWord = new HashMap<>();
        Map<String, Character> wordToChar = new HashMap<>();
        
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];
            
            if (charToWord.containsKey(c)) {
                if (!charToWord.get(c).equals(word)) {
                    return false;
                }
            } else {
                charToWord.put(c, word);
            }
            
            if (wordToChar.containsKey(word)) {
                if (wordToChar.get(word) != c) {
                    return false;
                }
            } else {
                wordToChar.put(word, c);
            }
        }
        
        return true;
    }
}

这段代码首先将字符串 s 分割成单词数组，然后使用两个哈希表来记录字符与单词之间的映射关系，并在存储映射关系的同时检查是否满足双向连接的对应规律。如果发现不匹配的情况，立即返回 false。如果遍历结束都没有发现不匹配，则返回 true。

四、时间复杂度和空间复杂度

1. 时间复杂度

分割字符串 s 成单词数组的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。这是因为分割操作需要遍历整个字符串。
遍历 pattern 和单词数组的时间复杂度是 O(m)，其中 m 是 pattern 的长度，因为 pattern 的长度与单词数组的长度相同，所以可以认为 m = n。
在遍历过程中，对于每个字符和单词，我们进行了哈希表的查找和插入操作，哈希表的查找和插入操作的平均时间复杂度是 O(1)。

综上所述，总的时间复杂度是 O(n) + O(m) * O(1) = O(n)，即线性时间复杂度。

2. 空间复杂度

存储单词数组的额外空间是 O(n)，因为单词数组的长度与字符串 s 的长度成正比。
两个哈希表 charToWord 和 wordToChar 的空间复杂度在最坏情况下是 O(n)，这是因为每个字符和单词都可能被映射到不同的项。

因此，总的空间复杂度是 O(n) + O(n) + O(n) = O(n)，即线性空间复杂度。

五、总结知识点

类定义 (class 关键字):
- 定义了一个名为 Solution 的类。
方法定义:
- 定义了一个公共方法 wordPattern，它接受一个字符串类型的参数 pattern 和另一个字符串类型的参数 s，并返回一个布尔值。
字符串操作:
- 使用 split 方法将字符串 s 按照空格分割成字符串数组 words。
条件语句 (if-else):
- 检查 pattern 的长度是否与 words 数组的长度相等，如果不相等，则直接返回 false。
数据结构 (HashMap):
- 使用 HashMap 来创建两个映射：charToWord 和 wordToChar，分别用于存储字符到单词的映射和单词到字符的映射。
循环结构 (for 循环):
- 使用 for 循环遍历 pattern 和 words 数组。
哈希表操作:
- 使用 containsKey 方法检查哈希表中是否已经包含了特定的键。
- 使用 get 方法从哈希表中获取与特定键关联的值。
- 使用 put 方法将键值对添加到哈希表中。
字符和字符串比较:
- 使用 equals 方法比较两个字符串是否相等。
- 使用 != 运算符比较两个字符是否不相等。
逻辑返回:
- 在发现不匹配的映射时，方法立即返回 false。
- 如果循环结束后没有发现不匹配，则返回 true。