🟢 有效的字母异位词

📝 题目描述

​ 给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。

​ 需要注意的是，若s和t中每个字符出现的次数都相同，则称s和t互为字母异位词。

📋 代码模板

class Solution {
    public boolean isAnagram(String s, String t) {

    }
}

💡 提示

1. $1<=s.length<=5\ast {10}^4$​
2. $1<=t.length<=5\ast {10}^4$
3. $s$ 和 $t$ 都仅包含小写字母

🚀 示例

🖊️ 题解

​ 如果 $s$ 和 $t$ 两个字符串的长度不相等，那么它们不可能互为字母异位词；相反，它们可能互为字母异位词。

​ 我们可以首先遍历字符串 $s$，并利用哈希表记录 $s$ 中的各字符与其出现次数的映射。其次，遍历字符串 $t$ 并查找哈希表，若字符在哈希表中的数量不足（小于1），则直接返回false。最后，在两轮遍历结束后，可返回true，此时说明了 $s$ 和 $t$ 中的各字符的出现次数是相同的，即互为异位词。

​ 由于字符串 $s$ 和 $t$ 都仅由小写英文字母组成，因此我们可以使用数组来替代哈希表，即使用数组的索引号来标识英文字母letter，计算公式为 letter - 'a'。这样一来，abc..xyz26个英文字母就分别对应了0 - 25。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] cmt = new int[26];
        for (char c : s.toCharArray()) {
            cmt[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            if (--cmt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

💭 复杂度分析

​ 基于哈希表的解决方案的复杂度分析如下。

• 时间复杂度：$O(n+m)$，其中 $n$ 为字符串 $s$ 的长度，$m$ 为字符串 $t$ 的长度。
• 空间复杂度：$O(C)$，其中 $C$ 为26，即全部小写英文字母的数量。