Ransom Note

Like0

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine. Each letter in magazine can only be used once.

The hash table idea is direct: count how many times each character appears in magazine, then spend those counts while walking through ransomNote. If any character runs out, the construction is impossible.

Budibadu uses this problem to reinforce counting and decrementing patterns, which come up all the time in string problems built on maps.

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false
Explanation: The letter a does not exist in the magazine.

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Explanation: There is only one a available.

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true
Explanation: The magazine provides two a characters.

Algorithm Flow

Recommendation Algorithm Flow for Ransom Note - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public boolean ransom_note(String ransomNote, String magazine) {
        Map<Character, Integer> count = new HashMap<>();
        for (char ch : magazine.toCharArray()) count.put(ch, count.getOrDefault(ch, 0) + 1);
        for (char ch : ransomNote.toCharArray()) {
            if (!count.containsKey(ch) || count.get(ch) == 0) return false;
            count.put(ch, count.get(ch) - 1);
        }
        return true;
    }
}

javascript

function ransom_note(ransomNote, magazine) {
    const count = {};
    for (const ch of magazine) count[ch] = (count[ch] || 0) + 1;
    for (const ch of ransomNote) {
        if (!count[ch]) return false;
        count[ch]--;
    }
    return true;
}

php

<?php
function ransom_note($ransomNote, $magazine) {
    $count = [];
    foreach (str_split($magazine) as $ch) {
        $count[$ch] = ($count[$ch] ?? 0) + 1;
    }
    foreach (str_split($ransomNote) as $ch) {
        if (!isset($count[$ch]) || $count[$ch] === 0) return false;
        $count[$ch]--;
    }
    return true;
}
?>

python

def ransom_note(ransomNote: str, magazine: str) -> bool:
    count = {}
    for ch in magazine:
        count[ch] = count.get(ch, 0) + 1
    for ch in ransomNote:
        if count.get(ch, 0) == 0:
            return False
        count[ch] -= 1
    return True

rust

use std::collections::HashMap;
fn ransom_note(ransom_note: String, magazine: String) -> bool {
    let mut count: HashMap<char, i32> = HashMap::new();
    for ch in magazine.chars() {
        *count.entry(ch).or_insert(0) += 1;
    }
    for ch in ransom_note.chars() {
        match count.get_mut(&ch) {
            Some(value) if *value > 0 => *value -= 1,
            _ => return false,
        }
    }
    true
}

typescript

function ransom_note(ransomNote: string, magazine: string): boolean {
    var count: { [key: string]: number } = {};
    var i: number;
    for (i = 0; i < magazine.length; i++) {
        var m = magazine.charAt(i);
        count[m] = (count[m] || 0) + 1;
    }
    for (i = 0; i < ransomNote.length; i++) {
        var r = ransomNote.charAt(i);
        if (!count[r]) return false;
        count[r]--;
    }
    return true;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

Ransom Note

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Hash Table Problems

Duplicate Indices Map

First Unique Character

Contains Duplicate

Valid Anagram

Two Sum Indices

Word Frequency Counter

Comments (0)

Join the Discussion