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

server/2024/9/23 5:55:45/

力扣经典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));}
}