力扣经典150题第四十一题：有效的字母异位词

力扣经典150题第四十二题：有效的字母异位词

引言

本篇博客介绍了力扣经典150题中的第四十二题：有效的字母异位词。题目要求判断给定的字符串 t 是否是字符串 s 的字母异位词。

字母异位词的定义是：如果 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

题目详解

给定两个字符串 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 仅包含小写字母

解题思路

为了判断字符串 t 是否是字符串 s 的字母异位词，可以使用两种方法：

1. 排序法： 将字符串 s 和 t 分别排序，然后比较排序后的结果是否相等。时间复杂度为 O(n log n)。

2. 哈希表法： 使用哈希表记录字符串 s 中每个字符出现的次数，然后遍历字符串 t，逐个减少哈希表中对应字符的计数。如果在减少过程中发现某个字符的计数小于零，或者最终哈希表中存在计数不为零的字符，则返回 false。

   • 进阶要求：如果输入字符串包含 unicode 字符，可以使用哈希表存储字符的计数。

具体步骤如下：

1. 如果 s 和 t 的长度不相等，直接返回 false。
2. 使用长度为 26 的整型数组 count 来记录字符出现的次数，索引为字符的 ASCII 值减去 ‘a’ 的 ASCII 值。
3. 遍历字符串 s，统计每个字符的出现次数。
4. 遍历字符串 t，逐个减少 count 中对应字符的计数。
5. 如果在减少过程中发现某个字符的计数小于零，或者最终 count 中存在计数不为零的字符，返回 false。
6. 如果遍历完成后没有发现不符合条件的情况，返回 true。

通过上述步骤，可以判断字符串 t 是否是字符串 s 的字母异位词。

代码实现

public class ValidAnagram {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] count = new int[26]; // 存储字符出现的次数，26个字母

        // 统计字符串 s 中每个字符出现的次数
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }

        // 逐个减少 count 中对应字符的计数
        for (char c : t.toCharArray()) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0) {
                return false; // 如果字符出现次数小于零，返回 false
            }
        }

        // 检查 count 中是否存在计数不为零的字符
        for (int num : count) {
            if (num != 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        ValidAnagram solution = new ValidAnagram();

        // 示例测试
        String s1 = "anagram";
        String t1 = "nagaram";
        System.out.println("s: " + s1 + ", t: " + t1);
        System.out.println("结果: " + solution.isAnagram(s1, t1));

        String s2 = "rat";
        String t2 = "car";
        System.out.println("s: " + s2 + ", t: " + t2);
        System.out.println("结果: " + solution.isAnagram(s2, t2));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

示例演示

展示了两个不同的示例测试，验证了字符串 t 是否是字符串 s 的字母异位词的功能。

复杂度分析

该解法的时间复杂度为 O(n)，其中 n 是字符串 s 的长度。空间复杂度为 O(1)，因为哈希表的大小是固定的（26 个字母）。