42.有效的字母异位词

题目

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

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路

两个字符串包含同样的字母，数量也相同，只是顺序不同，才算异位词。

思路: 统计每个字母出现的次数，两个字符串的统计结果相同则是异位词。

可以用一个长度为26的数组代表 a-z:

遍历s，对应位置+1
遍历t，对应位置-1

最后数组全为0则是异位词

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) return false
        val counts = IntArray(26)
        for (i in s.indices) {
            counts[s[i] - 'a']++
            counts[t[i] - 'a']--
        }
        return counts.all { it == 0 }
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        if (len1 != len2)
            return false;
        HashMap<Character, Integer> dic = new HashMap<>();
        for (int i = 0; i < len1; i++) {
            dic.put(s.charAt(i) , dic.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < len2; i++) {
            dic.put(t.charAt(i) , dic.getOrDefault(t.charAt(i), 0) - 1);
        }
        for (int val : dic.values()) {
            if (val != 0)
                return false;
        }
        return true;
    }
}

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        dic = defaultdict(int)
        for c in s:
            dic[c] += 1
        for c in t:
            dic[c] -= 1
        for val in dic.values():
            if val != 0:
                return False
        return True

复杂度分析:

时间复杂度 O(M+N) ：其 M , N 分别为字符串 s1, s2长度。当 s1, s2无相同字符时，三轮循环的总迭代次数最多为 2M+2N ，使用 O(M+N) 线性时间。
空间复杂度 O(1) ：由于字符种类是有限的（常量），一般 ASCII 码共包含 128 个字符，因此可假设使用 O(1) 大小的额外空间。

进阶: "字符"本身就包括 Unicode 字符，这里说的区别实际上是ASCII 字符和完整 Unicode 字符的区别。

ASCII字符只有128个字符，包括英文字母a-z、A-Z、数字、标点。

上面用固定数组IntArray(26)就能表示所有小写英文字母，因为只有26种可能。

'a' - 'a' = 0  -> counts[0]
'b' - 'a' = 1  -> counts[1]
'z' - 'a' = 25 -> counts[25]

而Unicode字符包含全球所有语言的字符，共100多万个码位:

中文: 你、好、世、界
日文：あ、い、う
韩文：가、나、다
emoji：😀、❤️、🎉
特殊符号：é、ñ、ü

这些字符无法用char - 'a'计算数组下标，也不可能开一个百万大小的数组。

因为上面说到只包含小写英文字母，所以IntArray(26)够用了

进阶问题把输入放开到任意Unicode字符，固定数组就失效了，必须用HashMap动态记录出现的字符。

所以进阶的解决方法就是把上面的固定26位数组表示，修改为用HashMap。

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        if (s.length != t.length) {
            return false
        }

        val hash = HashMap<Char, Int>()
        for (i in 0 .. s.lastIndex) {
            hash[s[i]] = (hash[s[i]] ?: 0) + 1
            hash[t[i]] = (hash[t[i]] ?: 0) - 1
        }
        return hash.values.all { it == 0 }
    }
}


class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> table = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) - 1);
            if (table.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为 s 的长度。
空间复杂度：O(n)。

下一题

邮箱：charon.chui@gmail.com
Good Luck!