TypeScript算法每日一题：赎金信（383）

作者：前端小王hs

阿里云社区博客专家/清华大学出版社签约作者✍/CSDN百万访问博主/B站千粉前端up主

题库：力扣
题目序号：383（简单）
题目：赎金信

给你两个字符串ransomNote 和 magazine，判断ransomNote能不能由magazine里面的字符构成。
如果可以，返回true；否则返回false。magazine中的每个字符只能在ransomNote中使用一次。

示例1：
输入：ransomNote = “a”, magazine = “b”
输出：false

示例2：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

解题思路：
通过两道示例可以得知，该题就是判断ransomNote的值是否包含在magazine中
解题的思路采取的是哈希表

可能有读者会问，为什么采取哈希表？采取这种方法的理由是什么？
①题目提到了magazine中的每个字符只能在ransomNote中使用一次，这是一个计算题，我们需要计算每个字符出现的次数，那么哈希表刚好可以满足这个需求
②如果对比使用数组，那可能需要采取二维数组的形式去记录字符出现的字数，如[[a,2],[b,1]]，提高了复杂度

其实有个最简单的判断思路就是，如果需要统计字符，那么可以首选哈希表

下面来看一下具体的实现过程
①先计算出magazine 中每个字符出现的次数，那么在JS或者TS中就是以对象的形式去模拟哈希表，也就是定义一个对象，对象的属性包括每个字符，属性值则是字符出现的数字

②遍历ransomNote字符串，通过下标获取字符，如果该字符不存在，那么return，反之在哈希表中的对应的字符的数字减1

这么说可能有些抽象，以这个示例2为例
可以得到如下的哈希表

let magazineCounts = {a:2b:1
}

这是第一步

然后就遍历ransomNote字符串
遍历第一次的时候，magazineCounts.a的数量从2变为1
遍历第二次的时候，magazineCounts.a的数量从1变为0
遍历结束，return true

解题代码：

function canConstruct(ransomNote: string, magazine: string): boolean {// 使用对象来记录 magazine 中字符的出现次数const magazineCounts: { [char: string]: number } = {};// 遍历 magazine 字符串，更新字符计数for (let i = 0; i < magazine.length; i++) {const char = magazine[i];magazineCounts[char] = (magazineCounts[char] || 0) + 1;}// 遍历 ransomNote 字符串，减去字符计数for (let i = 0; i < ransomNote.length; i++) {const char = ransomNote[i];  // 如果字符计数小于 0，说明字符不够if (!magazineCounts[char] || magazineCounts[char] < 1) {return false;}// 字符计数减1magazineCounts[char]--}return true;
};

解题过程示例：
略