LeetCode 242. 有效的字母异位词

上一篇博客：LeetCode 2923. 找到冠军 I——更好的解法

 写在前面：大家好！我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油，冲鸭！
 用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง

原题链接：242. 有效的字母异位词

题目信息

题目描述

 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的
字母异位词（字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次）。

示例 1

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2

输入: s = “rat”, t = “car”
输出: false

提示

$1\le s.length,t.length\le 5\ast 10^4$
s 和 t 仅包含小写字母

题解

解题思路1

 先判断两个字符串是否长度相等，如果长度不等那么一定不是 字母异位词。然后使用 HashMap 分别存储两个字符串中字母的出现次数，然后在遍历 HashMap 进行比较。这里要注意的一点就是不要直接进行比较，需要先将得到的值由 Integer 转换为 int，因为 Java 基本数据类型的包装类型的大部分都用到了缓存机制来提升性能。对于 Byte,Short,Integer,Long 这 4 种包装类默认创建了数值 [-128，127] 的相应类型的缓存数据。

 当我们使用 == 比较两个引用类型的对象时比较的是两个对象的内存地址，并不是实际的数值。因此如果直接使用 == 比较两个 引用类型对象 的值是否相等，对于 [-128，127] 范围内的两个 Integer对象 数值相同一定相等因为是同一个对象，但是范围之外会是两个不同的对象，内存地址不同导致即使数值相同也会由于不是同一个对象而不等。

解题代码

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            // 判断map中是否已经有了当前字符的统计，没有就初始化，有就将个数加一
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            sMap.put(sChar, sMap.getOrDefault(sChar, 0) + 1);
            tMap.put(tChar, tMap.getOrDefault(tChar, 0) + 1);
        }
        for (Character character : sMap.keySet()) {
            if (sMap.getOrDefault(character, 0).intValue() != tMap.getOrDefault(character, 0).intValue()) {
                return false;
            }
        }
        return true;
    }
}

解题思路2

 因为都是相同的字母个数，直接将两个字符串排序之后比较也是可以的。但是时间复杂度是 $O(n{\log }_{}n)$，不如思路 1 的时间复杂度为$O(n)$。

解题代码

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] strS = s.toCharArray();
        char[] strT = t.toCharArray();
        Arrays.sort(strS);
        Arrays.sort(strT);
        return Arrays.equals(strS, strT);
    }
}

注意点

 不要用 strS.equals(strT) 来比较 char[]，因为这样比较的是两个数组的地址是否相同，应该使用 Arrays类 中的 equals() 方法来进行比较。

strS.equals(strT)源码

 直接比较使用的是 Object类 中的 equals方法，对比是否是同一个引用。

public boolean equals(Object obj) {
    return (this == obj);
}

Arrays.equals(strS, strT)源码

 Arrays类 重写了 equals，比较两个对象的值是否相等。

public static boolean equals(char[] a, char[] a2) {
    if (a==a2)
        return true;
    if (a==null || a2==null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    for (int i=0; i<length; i++)
        if (a[i] != a2[i])
            return false;

    return true;
}