【面试经典150 | 哈希表】赎金信

写在前面

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

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

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

---

Tag

【哈希表】【数组】【字符串】【2024-01-07】

---

题目来源

383. 赎金信

---

题目解读

判断一个字符串是否可以用另一个字符串构成。

---

解题思路

方法一：哈希表

朴素的想法是利用两个哈希表分别统计 ransomNote 和 magazine 中出现的小写字符数量，然后比较两个哈希表中对应字符的数量；如果 magazine 中出现的小写字符数量小于 ransomNote 中出现的小写字符数量，直接返回 false；如果直到最后比较完所有出现的字符仍没有返回 false，则返回 true。

朴素的方法需要使用两个哈希表，可以优化一下使用一个哈希表。首先，使用一个哈希表 记录 magazine 中出现的小写字符数量；接着，遍历 ransomNote，将该字符串中出现在哈希表中的字符数量减一；最后，枚举哈希表，如果某个字符的数量小于 0，则直接返回 false，如果直到遍历完毕哈希表仍没有字符数量小于 0，则返回 true。

实现代码

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> cnts;
        for(char &c : magazine){
            ++ cnts[c];
        }
        
        for(char &c : ransomNote){
            --cnts[c];
            if(cnts[c] < 0){
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析

时间复杂度：$O(n+m)$，$n$ 为字符串 magazine 的长度，$m$ 为字符串 ransomNote 的长度。

空间复杂度：$O(\sum )$，$\sum$ 表示两个字符串中一共出现的不同字符数量，最大为 26。

方法二：数组模拟哈希表

可以使用数组来模拟哈希表，因为出现的都是小写字符，最多有 26 个，我们维护一个大小为 26 的数组 cnts，cnts[i] 表示字符 i + 'a' 出现的次数，这样就实现了哈希表的功能了。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> cnts(26);
        for (char c : magazine) {
            ++ cnts[c - 'a'];
        }

        for (char c : ransomNote) {
            -- 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
17

复杂度分析

时间复杂度：$O(n+m)$，$n$ 为字符串 magazine 的长度，$m$ 为字符串 ransomNote 的长度。

空间复杂度：$O(\sum )$，$\sum$ 表示两个字符串中一共出现的不同字符数量 26。

---

写在最后

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

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

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