Hackerrank: Cracking the Coding Interview – Hash Tables: Ransom Note

This solution just involves keeping track of how many words are available and how many are used. If at any point we are using more than are available then we know the answer is “No”. If all goes will after trying to print out the ransom note then we can safely print “Yes”.

Problem: https://www.hackerrank.com/challenges/ctci-ransom-note

Solution:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        String magazine[] = new String[m];
        for(int magazine_i=0; magazine_i < m; magazine_i++){
            magazine[magazine_i] = in.next();
        }
        HashMap<String,Integer> map = new HashMap<>();
        for (int i=0; i<magazine.length; i++) {
            if (map.containsKey(magazine[i])) {
                map.put(magazine[i], map.get(magazine[i]) + 1);
            } else {
                map.put(magazine[i], 1);
            }
        }
        String ransom[] = new String[n];
        boolean done = false;
        String ans = "Yes";
        for(int ransom_i=0; !done && ransom_i < n; ransom_i++){
            ransom[ransom_i] = in.next();
            if (map.containsKey(ransom[ransom_i])) {
                int x = map.get(ransom[ransom_i]);
                if (x > 1) {
                    map.put(ransom[ransom_i], x - 1);
                } else {
                    map.remove(ransom[ransom_i]);
                }
            } else {
                done = true;
                ans = "No";
            }
        }
        System.out.println(ans);
    }
}

Leave a Reply