今天分享的题目来源于 LeetCode 上第 242 号问题,是一道字符串的经典考题。
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
题目讲的是让你判断两个字符串中的字母是否一致,比如 示例1 中,s
包含字母 a、n、g、r、m
,而 t
中也包含 a、n、g、r、m
,都是只有这五个字母,并且 频次 相同,只是顺序不同。
看到 频次 这个词,你脑海中第一想法是什么?
没错,就是 哈希表 !
解法思路很简单。
false
s
中所有的字符出现个数使用 计数器 统计起来,存入一个大小为 26 的数组中(注意题目的说明)t
字符串,即遍历 t
时将对应的字母频次进行减少,如果期间 计数器 出现小于零的情况,则说明 t
中包含一个不存在于 s
中的字母,直接返回 false
。//@五分钟学算法
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
table[t.charAt(i) - 'a']--;
//小技巧:如果在任何时候遍历后者时,计数器低于零,那肯定说明
// t 中包含一个不存在于 s 中的字母
if (table[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}