leetcode 290 单词规律

zhaojun

2023 年 01 月 23 日

919 次浏览

暂无评论

457字数

默认分类

https://leetcode.cn/problems/word-pattern/description/

## 题目

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

## 思路

核心思路很简单，就是建立哈希表，key 为 pattern 中的每个规则字母，value 为用空格分别后的每个单词，如果 key 和 value 都不在哈希表中，则添加，如果其中一个在，则查看 key 和 value 是否匹配。

## 代码
```java
public boolean wordPattern(String pattern, String s) {
	Map<Character, String> map = new HashMap<>();
	String[] words = s.split(" ");

if (pattern.length() != words.length) {
		return false;
	}

for (int i = 0; i < words.length; i++) {
		char p = pattern.charAt(i);
		String word = words[i];

String val = map.get(p);
		if (val == null) {
			if (map.containsValue(word)) {
				return false;
			}
			map.put(p, word);
		} else if (!Objects.equals(word, val)) {
			return false;
		}
	}

return true;
}
```

不过需要注意的是，上方 `containsValue` 方法的时间复杂度是 O (n)，在 leetcode 中还见到一个极其简洁的解法：

```java
class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        if (words.length != pattern.length()) {
            return false;
        }
        Map<Object, Integer> map = new HashMap<>();
        for (Integer i = 0; i < words.length; i++) {
            if (map.put(words[i], i) != map.put(pattern.charAt(i), i)) {
                return false;
            }
        }

return true;
    }
}
```

这里利用的是 `map.put` 方法，如果 key 不存在，插入成功，返回 null；如果 key 存在，返回之前对应的 value。

最后修改：2023 年 01 月 23 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 290 单词规律

zhaojun • 2023 年 01 月 23 日

leetcode 290 单词规律

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

Shiro 学习 11 - 集成 Spring 之记住我

使用 Docker 快速安装 HTML5-Based Speedtest，可以准确的测试本地到 VPS 的网络速度

ZFile Docker 镜像构建过程

leetcode 257 二叉树的所有路径

Linux 命令行工具 ncdu 磁盘占用分析利器

leetcode 290 单词规律

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 290 单词规律

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款