LeetCode 图解 | 290 . 单词规律
文 | 景禹
来源：图解面试算法「ID: LeetCodeAnimation」
题目来源于 LeetCode 上第 290 号问题：单词规律。题目难度为 Easy，目前通过率为 42.4% 。
题目描述
给定一种规律
pattern和一个字符串str，判断str是否遵循相同的规律。 这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。 说明：你可以假设pattern只包含小写字母，str包含了由单个空格分隔的小写字母。
示例1：
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例2：
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
示例3：
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: false
示例4：
输入: pattern = "abba", str = "dog dog dog dog"
输出: false题目解析
这道题目主要考察哈希表和字符串的内容。可以将题目拆解为下面三步：
- 设置
pattern字符到单词（字符串str）的映射（哈希），使用HashMap()存储；使用HashSet()记录被使用过的单词 。 - 若单词个数和
pattern字符个数不匹配，返回false； - 遍历
pattern，同时对应的向前移动str中单词的指针，每次拆分出pattern中的一个字符， 判断：
- 如果该字符从未出现在哈希表中：
- 如果该字符对应的单词已被使用过 ，即`HashSet()`中包含该字符对应的单词，则返回false；
- 将该字符与其对应的单词做映射，加入哈希表中；标记该字符指向的单词为已使用，并加入`HashSet()`；
- 如果该字符在哈希表的映射单词与当前指向的单词不同，则返回false；
动画理解
代码实现
Java语言
class Solution {
public boolean wordPattern(String pattern, String str) {
HashMap<Character, String> map = new HashMap<>();
HashSet<String> set = new HashSet<>();
String[] array = str.split(" ");
if (pattern.length() != array.length) {
return false;
}
for (int i = 0; i < pattern.length(); i++) {
char key = pattern.charAt(i);
if (!map.containsKey(key)) {
if (set.contains(array[i])) {
return false;
}
map.put(key, array[i]);
set.add(array[i]);
} else {
if (!map.get(key).equals(array[i])) {
return false;
}
}
}
return true;
}
}复杂度分析
- 时间复杂度：遍历
pattren一遍，时间复杂度O(n) - 空间复杂度：需要申请
HashMap()与HashSet()，还需要将字符串str分割后存储起来。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录