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.
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.
- 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.
- 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.
- 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.
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"));
}
}
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