给定两个字符串 s
和 t
,编写一个函数来判断 t
是否是 s
的字母异位词。
注意:若 s
和 t
中每个字符出现的次数都相同,则称 s
和 t
互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 10^4
s
和t
仅包含小写字母
思路
方法1:自己写的
统计两个字符串中每个字符出现的次数,然后比较两个字符串中每个字符出现的次数是否一致。如果两个字符串中每个字符出现的次数都相等,则这两个字符串就是字母异位词,返回true;否则返回false
class Solution {
public boolean isAnagram(String s, String t) {
// 如果两个字符串长度不相等,则它们一定不是字母异位词,直接返回false
if(s.length() != t.length())
return false;
// 使用两个数组count1和count2来记录每个字母出现的次数
int count1[] = new int[26]; // 26个字符一一存放次数
int count2[] = new int[26];
// 将字符串s和t转换为字符数组
char[] ch1 = s.toCharArray();
char[] ch2 = t.toCharArray();
// 先统计字符串s中每个字符出现的次数
for(int i = 0; i < s.length(); i++) {
count1[ch1[i] - 'a']++; // 统计字符出现的次数,'a'-'a'为0,'b'-'a'为1,...,'z'-'a'为25
}
// 再统计字符串t中每个字符出现的次数
for(int j = 0; j < t.length(); j++) {
count2[ch2[j] - 'a']++;
}
int m = 0; // 记录每个字符出现的次数相等的次数
// 检查每个字符出现的次数是否相等
for(int i = 0; i < count1.length; i++) {
if(count1[i] == count2[i]) {
m++;
}
}
// 如果每个字符出现的次数相等的次数等于字符数组的长度,则说明两个字符串是字母异位词
if(m == count1.length)
return true;
else
return false;
}
}
方法2:计算两个字符串中字符的差值
参考作者:数据结构与算法
public boolean isAnagram(String s, String t) {
if (s.length() != t.length())
return false;
int[] letterCount = new int[26];
//统计字符串s中的每个字符的数量
for (int i = 0; i < s.length(); i++)
letterCount[s.charAt(i) - 'a']++;
//减去字符串t中的每个字符的数量
for (int i = 0; i < t.length(); i++) {
//如果当前字符等于0,直接返回false,
if (letterCount[t.charAt(i) - 'a'] == 0)
return false;
letterCount[t.charAt(i) - 'a']--;
}
return true;
}
方法3:先排序,在比较
先把两个字符串转化为字符数组,然后再对这两个字符数组进行排序,因为相同的字符在排序之后肯定是挨着的,最后再比较这两个排序后的数组的元素是否相同。
public boolean isAnagram(String s, String t) {
char[] sChar = s.toCharArray();
char[] tChar = t.toCharArray();
//对两个字符串中的字符进行排序
Arrays.sort(sChar);
Arrays.sort(tChar);
return Arrays.equals(sChar, tChar);
}
方法4:一次遍历
public boolean isAnagram(String s, String t) {
if (s.length() != t.length())
return false;
char[] cs = s.toCharArray();
char[] ct = t.toCharArray();
int[] map = new int[26];
int count = 0;
for (int i = 0; i < cs.length; i++) {
//出现了一个新的字符
if (++map[cs[i] - 'a'] == 1) {
count++;
}
//消失了一个新的字符
if (--map[ct[i] - 'a'] == 0) {
count--;
}
}
return count == 0;
}