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;isize();i++)
        {
            hash[s[i]-'a']++;
        }
        for(int i=0;isize();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)）完成了判断操作