Java Programs – LeetCode – Ransom Note – Solution 1

Problem Statement

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

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

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:

• You may assume that both strings contain only lowercase letters.

Solution

Sometimes reading a problem statement confuses you a lot like above. In short, we need to find if all characters of the first string are present in another string in the same count. For example, if first string contains 2 ‘a’ characters then second string also contains 2 ‘a’ characters. The order of characters does not matter.

Step by step logic

1. We need to find if all characters of first string are present in second string. It means the length of second string must be equal to or more than the length of first string. This should be first check before we think of actual logic.
2. Take first char of first string and check if second string contains that char or not. As the problem statement says that “Each letter in the magazine string can only be used once in your ransom note.” we need to remove the matched characters from second string.
3. We should also put some edge cases like if a given string is null.

Logic is simple and let’s do it using Java programming language.

Java Program

package Easy;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collector;
import java.util.stream.Collectors;

/*
Given an arbitrary ransom note string and another string containing letters from all the magazines, 
write a function that will return true if the ransom note can be constructed from the magazines ; 
otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

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:

You may assume that both strings contain only lowercase letters.

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

public class RansomNote {

	public static boolean canConstruct(String ransomNote, String magazine) {
		// Take length of first string
		int l1 = ransomNote.length();
		// Take length of second string
		int l2 = magazine.length();
		// Check if length of first string is greater than length of second string
		if (l1 > l2)
			// terminate execution as basic condition fails
			return false;
		// Iterate char by char of first string
		char[] ransomNoteChars = ransomNote.toCharArray();
		for (char charOfransomNote : ransomNoteChars) {
			// Check char is present in magazine string
			if (magazine.contains(Character.toString(charOfransomNote)))
				// If magazine contains char, replace that with empty string. 
				// I am using replaceFirst method to replace only first occurrence. 
				magazine = magazine.replaceFirst(Character.toString(charOfransomNote), "");
			else
				// If char is not present in magazine string then return false
				return false;
		}
		// If iteration is completed for each char it means all chars of ransom note is present in 
		// magazine note. 
		return true;

	}

	public static void main(String[] args) {
		System.out.println(canConstruct("aa", "aab"));
		System.out.println(canConstruct("aba", "aab"));
		System.out.println(canConstruct("abc", "ab"));
		System.out.println(canConstruct("b", "a"));
		System.out.println(canConstruct("amod maha", "mdoamaa h"));

	}

}

Output

true
true
false
false
true

You can clone above Git Repo from here.

You can subscribe to my YouTube channel RetargetCommon to learn from video tutorials.

If you have any doubt, feel free to comment below.
If you like my posts, please like, comment, share and subscribe.
#ThanksForReading
#HappyLearning

Find all Selenium related posts here, all API manual and automation related posts here, and find frequently asked Java Programs here.

Many other topics you can navigate through the menu.