文章目录
题目链接
https://leetcode-cn.com/problems/valid-anagram/
源代码 github 地址
https://github.com/YIMEng-0/DataStructure
1、题目要求
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
字母异位词的概念：
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
简单理解就是：两个字符串长度一样，构成字符串的每个字符只是排列的顺序不一样，含有的具体字符以及具体字符的个数是一样的；
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
2、思路分析
2.1 方法一
对于两个字符串里面的每个字符进行排序，然后比较排序后的结果，调用 Arrays.equals() 方法即可；
排序之前需要将字符串转换为 char 数组，这样子才能方便排序；
2.2 方法二
使用一个记录字符串中字符出现频次的数组，这个数组大小定义为 26 因为英语中存在 26 个字母，可以统计所有的字母字符串的情况；
对于字符串 s 来讲记录每个字符出现的次数，出现一次，记录频次的数组就会在相应的位置加一；
对于字符串 t 来讲，记录每个字符出现的次数，出现一次，在记录频次的数字就会在相应的位置减一；
如果记录频次的数组最终所有的元素都是 0 ，说明两个字符串是满足字母异位词的定义的；
3、执行代码
3.1、方法一的代码实现
public static boolean isAnagram(String s, String t) {
// 比较字符串的长度，长度不一致的话直接返回 false 即可
if (s.length() != t.length()) {
return false;
}
// 转换成为字符数组类型，方便对单个字符数组进行排序，查看里面的元素是否是相同的
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
// 进行排序处理
Arrays.sort(str1);
Arrays.sort(str2);
// 进行比较即可，调用了 Arrays 里面的比较函数
return Arrays.equals(str1, str2);
}
3.2、方法二的代码实现
public boolean isAnagram1(String s, String t) {
int[] record = new int[26];
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
for (int i = 0; i < str1.length; i++) {
record[str1[i] - 'a'] += 1;
}
for (int i = 0; i < str2.length; i++) {
record[str2[i] - 'a'] -= 1;
}
for (int i = 0; i < record.length; i++) {
if (record[i] != 0) {
return false;
}
}
return true;
}
4、问题反思
4.1、关于方法二中的 for 循环的理解
for (int i = 0; i < str1.length; i++) {
record[str1[i] - 'a'] += 1;
}
str1 是字符串 s 转换成为 char[] 数组的结果，这样子可以方便使用char[]数组对字符串中的每个字符进行操作；
i < str1.length;是对于 s 字符串中所有字符出现的总频次；可以对于 s 字符串中每个字符都统计到；
record[str1[i] - 'a'] += 1; 写法
等价于 record[str1[i] - 'a'] ++;
等价于record[str1[i] - 'a'] = record[str1[i] - 'a'] + 1;不过后者理解起来可能没有前者理解起来方便；
record 是一个 int 数组，目的就是统计 字符串s 以及 字符串t 两个字符串中字符出现的次数
- s 出现的字符出现一次，record 中对应的位置负责加一的操作；
- t 字符串出现的字符出现一次，record 中对应的位置负责减一的操作；
- 当 record 数组里面都是 0 的时候，增加的和减少的是相同的，说明满足字母异位词的定义；
5、小结
通过了排序的方式，以及使用记录数组的方式，可以实现字母异位词的判别。使用记录数组的方式，是对于这个问题的一个转换，大的字符串拆解成为小的字符，然后统计字符的个数，当统计字符个数的数组 record 元素都是 0 的时候，满足字母异位词的定义，输出结果为 true；