【面试经典150 | 哈希表】有效的字母异位词

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

---

Tag

【排序】【哈希表】【数组】

---

题目来源

242. 有效的字母异位词

---

题目解读

两个字符串中每个字符出现的次数都是一样的，则这两个字符串是字母异位词。现在需要判断给你的两个字符串是否为字符异位词。

---

解题思路

方法一：排序

我们可以对两个字符串进行升序排序，如果排序后两个字符相等，则互为字母异位词，返回 true，否则返回 false。

实现代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};
1
2
3
4
5
6
7
8

复杂度分析

时间复杂度：$O(nlogn)$，$n$ 为字符串 s 的长度。

空间复杂度：$O(nlogn)$，排序需要使用的额外空间。

方法二：哈希数组

我们使用一个数组来统计字符串中出现的字母数量，通常使用两个哈希数组分别统计两字符串中的字符数量，最后再比较对应字符出现的数量是否一致。

但是现在可以只用一个哈希数组，遍历 s 增加哈希数组中字符的数量，遍历 t 减少哈希数组中对应字符的数量，如果某个字符的数量小于 0 了，直接返回 false；如果直到遍历完毕 t 都没有遇到字符数量小于 0 的情况，最后返回 true。

实现代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) return false;

        vector<int> cnts(26, 0);
        for (char c : s) {
            ++cnts[c - 'a'];
        }
        for (char c : t) {
            --cnts[c - 'a'];
            if (cnts[c - 'a'] < 0) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度分析

时间复杂度：$O(n)$，$n$ 为字符串 s 的长度。

空间复杂度：$O(n$，哈希数组需要使用的额外空间。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。