383. Ransom Note

Solution

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const chars = [];
    
    for (const c of magazine) {
        const index = "z".charCodeAt(0) - c.charCodeAt(0);
        if (!chars[index]) {
            chars[index] = 1;
        } else {
            chars[index]++;
        }
    }
    
    for (const c of ransomNote) {
        const index = "z".charCodeAt(0) - c.charCodeAt(0);
        if (chars[index]) {
            if (--chars[index] < 0) {
                return false;
            }
        } else {
            return false;
        }
    }
    
    return true;
};

Complexity

  • Time Complexity: O(N+M), where N is the size of ransomNote and M is the size of magazine.
  • Space Complexity: O(N), where N is the size of chars.

All Solutions