Ransom Note

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.

Examples

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

Constraints

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine consist of lowercase English letters.

Solution

Method 1 - Using Map

Code

Java

public boolean canConstruct3(String ransomNote, String magazine) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : magazine.toCharArray()) {
        int count = map.containsKey(c) ? map.get(c) + 1 : 1;
        map.put(c, count);
    }
    for (char c : ransomNote.toCharArray()) {
        int newCount = map.containsKey(c) ? map.get(c) - 1 : -1;
        if (newCount == -1) return false;
        map.put(c, newCount);
    }
    return true;
}

Method 2 - Using Array as Map

The efficiency of the code is primarily due to using the ASCII value of each character in the string as an array index, allowing direct access and thereby significantly improving the algorithm's speed.

Code

Java

public boolean canConstruct2(String ransomNote, String magazine) {
	int[] table = new int[26];
	for (char c: magazine.toCharArray()) {
		table[c - 'a']++;
	}
	for (char c: ransomNote.toCharArray()) {
		if (--table[c - 'a']<0) {
			return false;
		}
	}
	return true;
}

If we don't want to do table[c-'a']:

public boolean canConstruct(String ransomNote, String magazine) {
	int[] table = new int[128];
	for (char c: magazine.toCharArray()) {
		table[c]++;
	}
	for (char c: ransomNote.toCharArray()) {
		if (--table[c]<0) {
			return false;
		}
	}
	return true;
}