题目描述

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

注意

• 可以假设所有字符串仅包含小写字母。

样例

输入：s = "anagram", t = "nagaram"
输出：true

输入：s = "rat", t = "car"
输出：false

说明

• 你可以假设字符串只包含小写字母。

进阶

• 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

算法

(哈希表) $O(n)$

1. 假设字符串只包含小写字母，则使用一个长度为 26 的数组当做哈希表，记录字母出现的次数。
2. 对于 s 往哈希表中增加相应字母的个数。
3. 对于 t 在哈希表中减少相应字母的个数。
4. 最后从 a 到 z 统计是否存在不为0的情况，如果有则返回 false。否则返 回true。

时间复杂度

• 线性遍历两个字符串，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间存储哈希表。

进阶

• 如果字符范围很大，则考虑将两个字符串排序，然后逐位比较。

C++ 代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> hash(26, 0);
        for (auto c : s)
            hash[c - 'a']++;
        for (auto c : t)
            hash[c - 'a']--;
        for (int i = 0; i < 26; i++)
            if (hash[i] != 0)
                return false;
        return true;
    }
};