46- 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b" 输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab" 输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab" 输出：true
提示：
1 <= ransomNote.length, magazine.length <= 105ransomNote和magazine由小写英文字母组成
方法一：暴力匹配法
这种方法通过逐个检查 ransomNote 中的字符是否存在于 magazine 中，并在找到后从 magazine 中移除该字符，确保每个字符只能使用一次。
function canConstruct(ransomNote: string, magazine: string): boolean {// 将magazine转换为数组，方便删除操作const magArray: string[] = magazine.split('');// 遍历ransomNote中的每个字符for (let i = 0; i < ransomNote.length; i++) {const char = ransomNote[i];// 查找字符在magArray中的索引const index = magArray.indexOf(char);// 如果没找到，返回falseif (index === -1) {return false;}// 从magArray中移除找到的字符magArray.splice(index, 1);}// 所有字符都找到，返回truereturn true;
}
方法二：哈希表统计法
使用哈希表分别统计 ransomNote 和 magazine 中各字符的出现次数，然后比较 ransomNote 中每个字符的次数是否不超过 magazine 中的次数。
function canConstruct(ransomNote: string, magazine: string): boolean {// 定义统计频率的函数function countFrequency(str: string): Map<string, number> {const freqMap = new Map<string, number>();for (const char of str) {freqMap.set(char, (freqMap.get(char) || 0) + 1);}return freqMap;}// 统计两个字符串的字符频率const ransomFreq = countFrequency(ransomNote);const magFreq = countFrequency(magazine);// 检查ransomNote中的每个字符频率是否超过magazinefor (const [char, count] of ransomFreq.entries()) {if (!magFreq.has(char) || magFreq.get(char)! < count) {return false;}}return true;
}
方法三：数组统计法
由于题目中字符是小写英文字母，可使用长度为 26 的数组代替哈希表，提高效率。
function canConstruct(ransomNote: string, magazine: string): boolean {// 创建长度为26的数组，对应a-z的频率const freqArray: number[] = new Array(26).fill(0);// 统计magazine中各字符的频率for (const char of magazine) {freqArray[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;}// 检查ransomNote中的字符频率for (const char of ransomNote) {const index = char.charCodeAt(0) - 'a'.charCodeAt(0);// 如果字符不存在或频率已用完，返回falseif (freqArray[index] === 0) {return false;}// 减少对应字符的频率freqArray[index]--;}return true;
}
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 方法一（暴力法） | O(m×n) | O(m) | m 是 magazine 长度，n 是 ransomNote 长度。每次查找和删除都是 O (m) 操作 |
| 方法二（哈希表） | O(m+n) | O(k) | k 是不同字符的数量，最多 26 个。统计和比较都是线性时间 |
| 方法三（数组法） | O(m+n) | O(1) | 使用固定长度数组，空间复杂度为常数，是三种方法中效率最高的 |
测试示例
// 示例1测试
console.log(canConstruct("a", "b")); // 输出: false// 示例2测试
console.log(canConstruct("aa", "ab")); // 输出: false// 示例3测试
console.log(canConstruct("aa", "aab")); // 输出: true
方法说明
-
暴力法是最直观的解法，但效率最低，因为每次查找和删除操作都是 O (m) 时间复杂度，m 是 magazine 的长度。
-
哈希表法通过统计字符频率进行比较，时间复杂度优化到 O (m+n)，空间复杂度取决于不同字符的数量，适用于各种字符集的情况。
-
数组法是针对本题的最优解法，利用字符范围固定（小写字母）的特点，使用固定长度数组统计频率，空间复杂度为 O (1)，时间复杂度也是线性的，是三种方法中效率最高的。
在实际应用中，如果字符集已知且范围较小，应优先选择数组法；如果字符集不确定，则使用哈希表法更为通用。