有效的字母异位词

发表于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，242. Valid Anagram

先看题目描述

DdE35R.png

大意就是给定两个字符串 s 和 t ，判断 t 是否是 s 的字母异位词

算法思路

哈希表

t 是 s 的异位词等价于 s 和 t 中的字符出现的种类和数量均相等，由于字符串 s 和 t 中出现的字符种类只包含 26 个小写字母，我们可以维护一个长度为 26 的频次数组 cnt，对于 s 中出现的字符 c，我们令 cnt[c - ‘a’]++；对于 t 中出现的字符 c，我们令 cnt[c - ‘a’]–，最后遍历 cnt 数组判断其中元素是否全为 0 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isAnagram(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m != n) return false;
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        int[] cnt = new int[26];
        for (int i = 0; i < m; i++) {
            cnt[ss[i] - 'a']++;
            cnt[tt[i] - 'a']--;
        }
        for (int num : cnt) {
            if (num != 0) return false;
        }
        return true;
    }
}

注意：这里预先把 s 和 t 转化为字符数组，而不是在后面使用 cnt[s.charAt(i) - ‘a’] 和 cnt[t.charAt(i) - ‘a’]，可以提高算法的运行效率

若将情况扩展，s 和 t 中不再只是包含小写字母，而是 unicode 字符，那么就不能使用频次数组 cnt 代替哈希表，而应该使用真正的哈希表，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}