[📝LeetCode #383] Ransom Note

#leetcode #java #100daysofcode #hashtable

🎀 The Problem

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:

Input: ransomNote = "aa", magazine = "ab"
Output: false

👩‍💻 My Answer

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Integer, Integer> hash = new HashMap();

        for (int i = 0; i < magazine.length(); i++) {
            int letter = magazine.charAt(i);
            if (!hash.containsKey(letter))
                hash.put(letter, 1);
            else
                hash.replace(letter, hash.get(letter) + 1);
        }

        for (int j = 0; j < ransomNote.length(); j++) {
            int letter = ransomNote.charAt(j);

            if (!hash.containsKey(letter))
                return false;

            int value = hash.get(letter);

            if (value == 1)
                hash.remove(letter);
            else
                hash.replace(letter, value - 1);
        }

        return true;
    }
}

Pro & Con

✖️ Runtime & Memory
✖️ Too long

💋 Ideal Answer

Approach - "Two Pointer"

I watched the YouTube video to understand better and realized that there is a way to add the frequency without using if statement to check whether the same character has been added before.

TheAnalyticGuy's Leetcode 383 Ransom Note (Java)

New Code

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Integer, Integer> hash = new HashMap();

        for (int i = 0; i < magazine.length(); i++) {
            int letter = magazine.charAt(i);

            hash.put(letter, hash.getOrDefault(letter, 0) + 1);
        }

        for (int j = 0; j < ransomNote.length(); j++) {
            int letter = ransomNote.charAt(j);

            if (!hash.containsKey(letter))
                return false;

            int value = hash.get(letter);

            if (value == 1)
                hash.remove(letter);
            else
                hash.replace(letter, value - 1);
        }

        return true;
    }
}