242.有效的字母异位词
难度:简单
给定两个字符串 s
和 t
,编写一个函数来判断 t
是否是 s
的字母异位词。
注意:若 s
和 t
中每个字符出现的次数都相同,则称 s
和 t
互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s
和t
仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
解题思路
使用一个 哈希表,把 s 字符串中的每个字符及出现个数存进去,再遍历 t 字符串,和哈希表中对应的数据进行比对即可。
注意一开始就对比一下字符串长度,可以直接排除一些错误情况。
我的代码(哈希表)
public boolean isAnagram(String s, String t) {
// 如果字符串长度不同,则它们不能是字母异位词
if (s.length() != t.length()){
return false;
}
// 使用HashMap来存储每个字符及其出现的次数
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 更新或增加字符的计数
// getOrDefault(key, default) 如果存在key, 则返回其对应的 value, 否则返回给定的默认值
map.put(c, map.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
if (map.containsKey(c) && map.get(c) > 0) {
map.put(c, map.get(c) - 1);
} else {
return false;
}
}
return true;
}
时间复杂度:O(n)
空间复杂度:O(n)
数组做法
思路概述
数组其实就是一个简单哈希表,而且这道题目中字符串只有小写字符,那么就可以定义一个数组 record,来记录字符串 s 里每个字符出现的次数。
record 数组的大小为 26 就可以了,初始化为 0,因为字符 a 到字符 z 的 ASCII 也是 26 个连续的数值。
把字符映射到数组的下标上,因为字符 a 到字符 z 的 ASCII 是 26 个连续的数值,所以字符 a 映射为下标 0,相应的字符 z 映射为下标 25。
在遍历字符串 s 的时候,只需要将 s[i] - 'a' 所在的元素做 + 1 操作即可,并不需要记住字符 a 的 ASCII,只要求出一个相对数值就可以了。 这样就将字符串 s 中字符出现的次数,统计出来了。
之后检查字符串 t 中是否出现了这些字符,在遍历字符串 t 的时候,先判断 record 数组中对应索引处的值是否大于 0,如果不大于 0,说明 t 中出现了 s 中没有或者不足的字符,此时返回 false。
如果索引处的值大于 0,则只需要对 t[i] - 'a' 所在的元素做 - 1 操作即可。
最后如果 record 数组所有元素都为 0,说明字符串 s 和 t 是字母异位词,返回 true。
时间复杂度为 O(n),空间上因为定义是的一个常量大小的辅助数组,所以空间复杂度为 O(1)。
注意一开始就对比一下字符串长度,可以直接排除一些错误情况。
代码展示
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
record[s.charAt(i) - 'a']++;// 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
}
for (int i = 0; i < t.length(); i++) {
if (record[t.charAt(i) - 'a'] > 0) {
record[t.charAt(i) - 'a']--;
} else {
return false;
}
}
return true;
}
时间复杂度:O(n)
空间复杂度:O(1),因为定义是的一个常量大小的辅助数组
总结
数组就是简单的哈希表,但是数组的大小不是无限开辟的。