Ransom Note - Leetcode Solution

Problem:

Given two strings, ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example:

Input: ransomNote = "aa", magazine = "aab" Output: true

Input: ransomNote = "aaa", magazine = "aab" Output: false

Solution:

To solve this problem, we can use a HashMap to store the frequency of each character in the magazine string. Then, we can iterate through the ransomNote string and check if each character exists in the HashMap and if its frequency is greater than 0. If it is, we decrement its frequency and move on to the next character in the ransomNote string. If a character does not exist in the HashMap or its frequency is 0, we return false. Otherwise, we return true at the end of the iteration.

Here's the detailed implementation of our solution:

class Solution { public boolean canConstruct(String ransomNote, String magazine) { HashMap<Character, Integer> map = new HashMap<>(); for(char c : magazine.toCharArray()){ map.put(c, map.getOrDefault(c, 0) + 1); } for(char c : ransomNote.toCharArray()){ if(!map.containsKey(c) || map.get(c) == 0){ return false; }else{ map.put(c, map.get(c) - 1); } } return true; } }

Here, we first create a HashMap called map to store the frequency of each character in the magazine string. We iterate through each character in the magazine string and add its frequency to the map using getOrDefault() method. This helps us keep track of the frequency of each character.

Next, we iterate through each character in the ransomNote string and check if it exists in the map and if its frequency is greater than 0. If it is, we decrement its frequency in the map using map.get(c) - 1 and move on to the next character in the ransomNote string. If it does not exist in the map or its frequency is 0, we immediately return false. If we reach the end of the iteration without any issues, we return true.

The time complexity of this solution is O(n) where n is the length of the ransomNote string, since we iterate through each character in both the ransomNote and the magazine strings. The space complexity is also O(n) where n is the length of the magazine string, since we store each character's frequency in the map.

1