题型:字符串、哈希表、排序
链接:242. 有效的字母异位词 - 力扣(LeetCode)
来源:LeetCode
题目描述
给定两个字符串 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 * 104
s
和t
仅包含小写字母
题目思路
一开始因为看到是个哈希表的题目,所以想用哈希表来做。但平时都是用数组来实现哈希结构,这种【英文字母】1的,所以考虑用一个int[26]来表示26个英文字母的出现次数,然后当某个字母的次数为-1,代表次数不够用(即不满足条件)
但看到题解,发现有一种“暴力法”——排序两个字符串,然后比较——归根结底还是因为字母异位词的字母以及个数是相同的,所以排序后字符串如果相同,那就是字母异位串
C++代码
先上【排序】代码
class Solution {
public:
bool isAnagram(string s, string t) {
//排序后看看两个字符串是否相等
if(s.length() != t.length())
return 0;
sort(s.begin(),s.end());
sort(t.begin(),t.end());
return s==t;
}
};
【数组哈希】代码
class Solution {
public:
bool isAnagram(string s, string t) {
// 哈希表实现
// 长度不等一定不对
if(s.length() != t.length())
return 0;
//数组实现哈希结构
int number[26]{};
for(auto cHar : s)
{
number[cHar-'a']++;
}
for(int i=0;i<t.length();i++)
{
--number[t[i]-'a'];
if(number[t[i]-'a']<0)
return 0;
}
return 1;
}
};
结算页面
感觉这样比较好