力扣经典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 的字母异位词，可以使用两种方法：
- 排序法： 将字符串 s 和 t 分别排序，然后比较排序后的结果是否相等。时间复杂度为 O(n log n)。
- 哈希表法：使用哈希表记录字符串s中每个字符出现的次数，然后遍历字符串t，逐个减少哈希表中对应字符的计数。如果在减少过程中发现某个字符的计数小于零，或者最终哈希表中存在计数不为零的字符，则返回false。
- 进阶要求：如果输入字符串包含 unicode 字符，可以使用哈希表存储字符的计数。
具体步骤如下：
- 如果 s 和 t 的长度不相等，直接返回 false。
- 使用长度为 26 的整型数组 count 来记录字符出现的次数，索引为字符的 ASCII 值减去 ‘a’ 的 ASCII 值。
- 遍历字符串 s，统计每个字符的出现次数。
- 遍历字符串 t，逐个减少 count 中对应字符的计数。
- 如果在减少过程中发现某个字符的计数小于零，或者最终 count 中存在计数不为零的字符，返回 false。
- 如果遍历完成后没有发现不符合条件的情况，返回 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)); } }
示例演示
展示了两个不同的示例测试，验证了字符串 t 是否是字符串 s 的字母异位词的功能。
复杂度分析
该解法的时间复杂度为 O(n)，其中 n 是字符串 s 的长度。空间复杂度为 O(1)，因为哈希表的大小是固定的（26 个字母）。
