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 字符串，和哈希表中对应的数据进行比对即可。

注意一开始就对比一下字符串长度，可以直接排除一些错误情况。

我的代码（哈希表）

java

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)。

注意一开始就对比一下字符串长度，可以直接排除一些错误情况。

代码展示

java

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)，因为定义是的一个常量大小的辅助数组

总结

数组就是简单的哈希表，但是数组的大小不是无限开辟的。

242.有效的字母异位词 ​

解题思路 ​

我的代码（哈希表） ​

数组做法 ​

思路概述 ​

代码展示 ​

总结 ​