Valid Anagram

242. 有效的字母异位词

分析

使用哈希表统计字符频次
- 分别遍历 s 和 t，统计每个字符的出现次数
- 使用两个哈希表 hashS 和 hashT 存储字符频次
比较两个哈希表是否相等
- 如果两个哈希表相等，说明两个字符串是字母异位词
- 如果不相等，说明字符种类或字符次数不同，返回 false
时间复杂度：O(n)
- 遍历两个字符串各一次
空间复杂度：O(n)
- 使用哈希表存储字符频次

时间复杂度

总时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution
{
public:
    bool isAnagram(string s, string t)
    {
        std::unordered_map<char, int> hashS, hashT;

        // 1. 统计字符串 s 的字符频次
        for (char c : s)
            ++hashS[c];

        // 2. 统计字符串 t 的字符频次
        for (char c : t)
            ++hashT[c];

        // 3. 比较两个哈希表是否相等
        return hashS == hashT;
    }
};