📃 题目描述

题目链接：

• 剑指 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，最后遍历了一遍哈希表/数组。