题目

给定两个字符串 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 字符怎么办？你能否调整你的解法来应对这种情况？

思路

先看暴力的解法，两层 for 循环，同时还要记录字符是否重复出现，很明显时间复杂度是 O(n^2) 。暴力的方法这里就不做介绍了，直接看一下有没有更优的方式。

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

如果对哈希表的理论基础关于数组，set，map不了解的话可以看这篇：哈希表理论基础。

题目规定 s 和 t 仅包含小写字母。那么我们需要把字符映射到数组也就是哈希表的索引下表上。

我们知道，字符 a 到字符 z 的 ASCII 也是 26 个连续的数值，所以可以将字符 a 映射为下表 0，相应的字符 z 映射为下表 25。

我们可以定义一个长度为 26 的数组，记作 record，用来记录字符串 s 里字符出现的次数。

在遍历字符串 s 的时候，只需要将 s[i] - ‘a’ 所在的元素做 +1 操作即可，并不需要记住字符 a 的 ASCII，只要求出一个相对数值就可以了。 这样就将字符串 s 中字符出现的次数，统计出来了。

那么，我们同样在遍历字符串 t 的时候，对 t 中出现的字符映射哈希表索引上的数值再做 -1 的操作。

最后检查一下，record 数组如果有的元素不为 0 ，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符，return false。反之则 return true 。

时间复杂度为 O(n) ，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为 O(1) 。

下面举个例子，模拟一下字符串 s= “aee”, t = “eae” 时的操作动画：

答案

Java

class Solution {
    public boolean isAnagram(String s, String t) {
        // 辅助数组
        int[] record = new int[26];

        // 统计字符串 s 中字符出现的次数，辅助数组对应元素 +1
        for (char c : s.toCharArray()) {
            record[c - 'a'] += 1;
        }

        // 统计字符串 t 中字符出现的次数，辅助数组对应元素 -1
        for (char c : t.toCharArray()) {
            record[c - 'a'] -= 1;
        }

        // 辅助数组中如果有元素不为 0，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符，return false。
        for (int i : record) {
            if (i != 0) {
                return false;
            }
        }

        //  t 是 s 的字母异位词，return true。
        return true;
    }
}

进阶

class Solution {
    public boolean isAnagram(String s, String t) {
        // 辅助数组
        HashMap<Character, Integer> map = new HashMap<>(26);

        // 统计字符串 s 中字符出现的次数，辅助数组对应元素 +1
        for (Character c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // 统计字符串 t 中字符出现的次数，辅助数组对应元素 -1
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) - 1);
        }

        // 辅助数组中如果有元素不为 0，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符，return false。
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for (Map.Entry<Character, Integer> entry : entries) {
            if (entry.getValue() != 0) {
                return false;
            }
        }

        //  t 是 s 的字母异位词，return true。
        return true;
    }
}

REF

https://leetcode-cn.com/problems/valid-anagram/

算法总纲

242.有效的字母异位词

题目

思路

答案

Java

REF