有效的字母异位词
# 📃 题目描述
题目链接:
- 剑指 Offer II 032. 有效的变位词 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 242. 有效的字母异位词 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s
和 t
中每个字符出现的次数都相同且字符顺序不完全相同,则称s
和 t
互为变位词(字母异位词)。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
示例 3:
输入: s = "a", t = "a"
输出: false
# 🔔 解题思路
Hash 表的 key 存储字符,value 存储该字符出现的次数
- 先处理字符串 s 将其存入 Hash 表
- 然后再处理字符串 t,若 t 中的字符存在于 Hash 表中,则该字符对应的 value 减 1
- 一旦发现 value < 0,则立即返回 false;
- 若直到 t 全部处理完毕后,Hash 表中仍然存在 value > 0,则返回 false;
class Solution {
public boolean isAnagram(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
if (s.length() != t.length() || s.equals(t)) {
return false;
}
// 处理第一个字符串 s
for (char ch : s.toCharArray()) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
// 处理第二个字符串 t
for (char ch : t.toCharArray()) {
// 如果 map 中不存在该字符
if (!map.containsKey(ch)) {
return false;
} else {
// map 中存在该字符但 value 已经为 0
if (map.get(ch).equals(0)) {
return false;
}
map.put(ch, map.get(ch) - 1);
}
}
// 若直到 t 全部处理完毕后,Hash 表中仍然存在 value > 0,则返回 false
for (Character ch : map.keySet()) {
if (map.get(ch) > 0) {
return false;
}
}
return true;
}
}
进一步思考下,其实数组就是一个简单的哈希表,对于哈希表中的 key,如果哈希值比较连续且固定,我们可以用数组的下标来等同。事实上,如果数组是适用的,那么最好就不要用哈希表,因为使用哈希表的空间消耗要比数组大,哈希表可能要维护红黑树而且还要做哈希函数,数据量大的话就能体现出来差别了。
这个题目中的 key 存储的就是 26个字母,那我们只需要将其转成 int 作为数组的下标即可:
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] num = new int[26];
// 处理第一个字符串 s
for (char ch : s.toCharArray()) {
num[ch - 'a'] += 1;
}
// 处理第二个字符串 t
for (char ch : t.toCharArray()) {
num[ch - 'a'] -= 1;
}
// 若 t 全部处理完毕后,数组中仍然存在 value != 0,则返回 false
for (int i : num) {
if (i != 0) {
return false;
}
}
return true;
}
}
# 💥 复杂度分析
- 空间复杂度:数组和哈希表的空间复杂度是一样的,都是 O(N)
- 时间复杂度:两种方法的时间复杂度也都是一样的 O(N),因为我们就是遍历了一遍字符串 s,遍历了一遍字符串 t,最后遍历了一遍哈希表/数组。
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10