Ransom Note

https://leetcode.com/problems/ransom-note/

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

Solution:

In this problem, we are going to use two technics: "dictionary" + "char/byte manipulation"

The main idea is to prepare two dictionaries for magazine and ransomNote characters and then compare the count of characters in ransonNote dictionary.

How we can create dictionaries? We know that in this problem, we will have only lower letters from eng. alphabet. That is why we can create a char[26] array as a dictionary.

But how we can put elements there? currentChar - 'a' gives us index of currentChar in alphabet. Yes, yes, to wisdom. Please remember it.

Or if you are not familiar with char arrays, you can use the simple hash map.

  public boolean canConstruct(String ransomNote, String magazine) {
//     Map<Character, Integer> ransomMap = new HashMap();
     
//     for(char c : ransomNote.toCharArray()){
//       if (ransomMap.containsKey(c)){
//         ransomMap.put(c, ransomMap.get(c) + 1);
//       } else {
//         ransomMap.put(c, 1);
//       }
//     }
//     for (char c : magazine.toCharArray()){
//       if (ransomMap.containsKey(c)){
//         ransomMap.put(c, ransomMap.get(c) - 1);
//       }
//     }
     
//     for(Integer i : ransomMap.values()){
//       if (i > 0){
//         return false;
//       }
//     }
//     return true;
    char[] ransom = new char[26];
    char[] dict = new char[26];
     
    for (char c : ransomNote.toCharArray()){
      ransom[c - 'a'] += 1;
    }
    for (char c : magazine.toCharArray()){
      dict[c - 'a'] += 1;
    }
     
    for(int i = 0; i < ransom.length; i ++){
      if (ransom[i] > dict[i]){
        return false;
      }
    }
    return true;
  }