LeetCode 242 - 有效的字母异位词
题目描述
给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的 字母异位词。
解题思路
要判断两个字符串是否为字母异位词，可以统计两个字符串中每个字符的数量，然后比较两个计数器是否相等。可以利用哈希表来记录每个字符出现的次数，遍历第一个字符串时增加计数，遍历第二个字符串时减少计数。最终检查哈希表中所有的计数器是否为0，如果是，则说明两个字符串是字母异位词。
算法实现
C++实现
class Solution {
public:
bool isAnagram(string s, string t) {
int hash[26]={0};
for(int i=0;i<s.size();i++)
{
hash[s[i]-'a']++;
}
for(int i=0;i<t.size();i++)
{
hash[t[i]-'a']--;
}
for(int i=0;i<26;i++)
{
if(hash[i]!=0)
{
return false;
}
}
return true;
}
};复杂度分析
- 时间复杂度：O(n)，其中 n 为字符串的长度。遍历字符串两次，哈希表的插入和查询操作的时间复杂度均为 O(1)。
- 空间复杂度：O(1)，由于只使用了常数额外空间，哈希表的大小最多为26个小写字母。
总结
通过使用哈希表记录字符出现的次数，我们可以高效地判断两个字符串是否为字母异位词。这种方法减少了额外内存的消耗，同时在线性时间复杂度内（O(n)）完成了判断操作