题目描述
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
样例
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
思路(暴力)
要想保证两个词是有效的字母异位词,那么首先要保证两个词的长度相等,如果长度不相等则直接返回false
然后对两个单词进行排序
排序之后可以遍历每个单词看是否相等,也可以直接调用返回s.equals(t);
C++ 代码
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
if(s.size() != t.size())
return false;
else
{
for(int i = 0; i < s.size(); i ++)
{
if(s[i] != t[i])
return false;
}
}
return true;
}
};
思路(哈希表)
首先还是先判断两个词的长度是否相等,如果相等则继续,不相等则返回false
然后创建一个哈希表
先遍历s字符串,存储串中的每一个字母及其数量
然后遍历t字符串,使每一个单词的数量减一,如果两个词是字母异位词,那么每个字母的数量必定相等,最后哈希表中的每个单词的数量应该为0,如果某个字母的数量小于0则返回false
如果以上代码都没执行则返回true
C++ 代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size())
return false;
unordered_map<char, int> hash;
for(int i = 0; i < s.size(); i ++)
hash[s[i]] ++;
for(int i = 0; i < t.size(); i ++)
{
hash[t[i]] --;
if(hash[t[i]] < 0)
return false;
}
return true;
}
};