We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Hash Tables: Ransom Note
  2. Discussions

Hash Tables: Ransom Note

  • helioalb
     + 10 comments

    One possible java solution:

    public class Solution {
    Map<String, Integer> magazineMap;
    Map<String, Integer> noteMap;
    
    public Solution(String magazine, String note) {
        magazineMap = new HashMap<String, Integer>();
        noteMap = new HashMap<String, Integer>();
        
        for (String word : magazine.split(" ")) {
            Integer i = magazineMap.get(word);
            
            if (i == null) {
                magazineMap.put(word, 1);
            } else {
                magazineMap.put(word, i + 1);
            }
        }
        
        for (String word : note.split(" ")) {
            Integer i = noteMap.get(word);
            
            if (i == null) {
                noteMap.put(word, 1);
            } else {
                noteMap.put(word, i + 1);
            }
        }
    }
    
    public boolean solve() {
        for (Map.Entry<String, Integer> entry : noteMap.entrySet()) {
            Integer i = magazineMap.get(entry.getKey());
            
            if (i == null) {
                return false;
            } else {
                if (entry.getValue() > i) {
                    return false;
                }
            }
        }
        return true;
    }

    • Karbon
       + 1 comment

      This changes the inital code but is optimized

      Map<String, Integer> magazineMap;
boolean isValid;

public Solution(String magazine, String note) {
    magazineMap = new HashMap<String, Integer>();
    isValid = true;

    for (String word : magazine.split(" ")) {
        Integer i = magazineMap.get(word);

        if (i == null) {
            magazineMap.put(word, 1);
        } else {
            magazineMap.put(word, i + 1);
        }
    }

    for (String word : note.split(" ")) {
        Integer i = magazineMap.get(word);

        if (i == null || magazineMap.get(word) == 0) {
            isValid = false;
            break;
        } else {
            magazineMap.put(word, i - 1);
        }
    }
}

public boolean solve() {
    return isValid;
}

      • ajay443
         + 1 comment

        I still don't getting why Hashmap for this problem.

        • Karbon
           + 3 comments

          HashMaps solves the problem in O(n) time. You can add the words to an array and sort the array, but that would be O(n log n)

          • RA1003
             + 0 comments

            every time a new word is being checked from magazine so obviously more than once the condition i==null will be true.That means multiple words are getting their value as 1.

    • matabc
       + 1 comment

      Here is mine:

      try (final Scanner in = new Scanner(System.in)) {
			final int numMagazineWords = in.nextInt();
			final int numRansomWords = in.nextInt();
			final Map<String, Integer> magazineWordsToCounts = new HashMap<>();
			IntStream.range(0, numMagazineWords).mapToObj(i -> in.next())
					.forEach(word -> magazineWordsToCounts.merge(word, 1, (a, b) -> a + b));
			final Map<String, Integer> ransomWordsToCounts = new HashMap<>();
			IntStream.range(0, numRansomWords).mapToObj(i -> in.next())
					.forEach(word -> ransomWordsToCounts.merge(word, 1, (a, b) -> a + b));
			boolean ransomNotePossible = true;
			for (final String word : ransomWordsToCounts.keySet()) {
				if (ransomWordsToCounts.get(word) > magazineWordsToCounts.getOrDefault(word, 0)) {
					ransomNotePossible = false;
					break;
				}
			}
			if (ransomNotePossible) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}

      • [deleted]Challenge Author         + 0 comments

        Thanks, i worked with your solution for some time of the day. Greets

    • Nobody_me
       + 0 comments

      Yea your program works fine. I just have one question why is there a check called if(entry.getValue()>i)

      what does it do?

    • keshav1905
       + 0 comments

      new to hashtables, could someone please explain the constructor?

    • nivi_kpm95
       + 1 comment

      if (entry.getValue() > i) { return false; } Can anyone explain this part here pls..

      • sidakadjpoison
         + 0 comments

        notice that in the note "two" is required 2 times so if number of "two" in note is greater than number of "two" in magazine then return false.

    • sirisrk54
       + 1 comment

      hello sir can u tell what get method does in this line.. Integer i = noteMap.get(word);

      • sidakadjpoison
         + 1 comment

        noteMap contains String and Integer key value pair. So this line gets the Integer value of "word" key.

        • sirisrk54
           + 0 comments

          ya sir thank you :)

    • tatianaensslin
       + 0 comments

      you dont need two hash maps for this problem.

    • mschumacher
       + 1 comment

      Excellent. Simple and effective. My Solution is very similar, however, I opted for Lambdas to make use of the HashMap's built in methods (merge). See below (Note: Default imports excluded for brevity.):

      import java.util.HashMap;
import java.util.function.*;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        HashMap<String, Integer> magazine = new HashMap<>();
        BiFunction<Integer, Integer, Integer> val_merge = 
            (init_val, new_val) -> { return init_val + new_val; }; 
         
        for(int i = 0; i < m; i++) {
            String word = in.next();
            magazine.merge(word, 1, val_merge);
        }

        String result = "Yes";
        
        for(int ransom_i=0; ransom_i < n; ransom_i++){
            String word = in.next();
            if(magazine.merge(word, -1, val_merge) < 0) {
                result = "No";
                break;
            }
        }
        
        System.out.println(result);
    }
}

      • mattheweaston21
         + 0 comments

        I really didn't expect that to work but it does

    • williamliu14789
       + 0 comments

      i managed to produce solution but i have 2 runtime error, anyone help?

          for(String x : new HashSet<>(note))
        if(Collections.frequency(note, x)>Collections.frequency(magazine, x)){
            System.out.println("No");
            return;
        }
    System.out.println("Yes");

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in