383 赎金信

题目

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

题解

1. 分别遍历 ransomNote 和 magazine，把里面的字符存入哈希表里，再一次遍历当 magazine 的哈希表里不包含 ransomNote 的字符或者字符的值为 0 时，说明需要返回 false。

TIP

执行用时：96 ms, 在所有 JavaScript 提交中击败了 88.37% 的用户
内存消耗：41.1 MB, 在所有 JavaScript 提交中击败了 55.32% 的用户

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    let hash1 = new Map()
    let hash2 = new Map()

    for(let i=0;i<ransomNote.length;i++) {
        let item = ransomNote[i]
        let val = hash1.get(item)
        hash1.set(item, val == undefined ? 1 : val + 1)
    }
    for(let i=0;i<magazine.length;i++) {
        let item = magazine[i]
        let val = hash2.get(item)
        hash2.set(item, val == undefined ? 1 : val + 1)
    }
    for(let i=0;i<ransomNote.length;i++) {
        let key = ransomNote[i]
        if(hash2.get(key) == undefined) {
            return false
        } else if (hash2.get(key) === 0) {
            return false
        }

        hash2.set(key, hash2.get(key) - 1)
    }

    return true
};

• 时间复杂度： `O(n)`，分别使用三个 for循环`
• 空间复杂度： `O(n)`，使用两个 Map 结构来储存值
• 最好情况： 尽早的发现不能构成时
• 最坏情况： 在完成整个循环后，能够构成

2. 把 ransomNote 里的字符 对 magazine 进行替换操作，当 字符不存在时，则返回 false，否则返回 true

TIP

执行用时：100 ms, 在所有 JavaScript 提交中击败了 83.06% 的用户
内存消耗：44.7 MB, 在所有 JavaScript 提交中击败了 5.11% 的用户

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    for(let i=0;i<ransomNote.length;i++) {
        let item = ransomNote[i]
        if(!magazine.includes(item)) return false
        magazine = magazine.replace(item, '')
    }

    return true
};

• 时间复杂度： `O(n^2)`，for循环内使用 `includes` 方法
• 空间复杂度： `O(1)`，使用变量储存值，不过每次会对 magazine 进行重新赋值操作
• 最好情况： 尽早的发现没有可用的值
• 最坏情况： 在循环后，全部可以使用