383. Ransom Note

Problem

Given two strings ransomNote and magazine, return true** if ransomNote can be constructed by using the letters from magazine and false otherwise**.

Each letter in magazine can only be used once in ransomNote.

  Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

  Constraints:

• 1 <= ransomNote.length, magazine.length <= 105

• ransomNote and magazine consist of lowercase English letters.

Solution

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    var map = {};
    for (var i = 0; i < magazine.length; i++) {
        map[magazine[i]] = (map[magazine[i]] || 0) + 1;
    }
    for (var j = 0; j < ransomNote.length; j++) {
        if (!map[ransomNote[j]]) return false;
        map[ransomNote[j]] -= 1;
    }
    return true;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).