I am trying the ransom note challenge:
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 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
here is my solution:
public static boolean canConstruct(String ransomNote, String magazine) {
ArrayList<Character> ransomChar = new ArrayList<Character>();
ArrayList<Character> magazineChar = new ArrayList<Character>();
if (ransomNote.length() == 1 && magazine.length() == 1) {
if (ransomNote.equals(magazine)) {
return true;
}
return false;
}
else if (ransomNote.length() == 1 && magazine.length() > 1) {
for (int i = 0; i < magazine.length(); i ) {
if (magazine.charAt(i) == ransomNote.charAt(0)) {
return true;
}
}
return false;
}
else if (ransomNote.length() > 1 && magazine.length() > 1) {
for (int i = 0; i < ransomNote.length(); i ) {
ransomChar.add(ransomNote.charAt(i));
}
for (int i = 0; i < magazine.length(); i ) {
magazineChar.add(magazine.charAt(i));
}
while (ransomChar.size() > 1) {
for (int i = 0; i < ransomChar.size(); i ) {
boolean flag = false;
for (int j = 0; j < magazineChar.size(); j ) {
if (ransomChar.get(i).equals(magazineChar.get(j))) {
ransomChar.remove(i);
magazineChar.remove(j);
flag = true;
}
else if (ransomChar.isEmpty()) {
return true;
}
}
if (!flag) {
return false;
}
}
}
if (ransomChar.size() == 1 && magazineChar.size() == 1) {
if (ransomChar.equals(magazineChar)) {
return true;
}
return false;
}
else if (ransomChar.size() == 1 && magazineChar.size() > 1) {
for (int i = 0; i < magazineChar.size(); i ) {
if (ransomChar.get(0).equals(magazineChar.get(i))) {
return true;
}
}
return false;
}
}
return false;
}
I am passing most test cases but it throws an error at input:
"bg"
"efjbdfbdgfjhhaiigfhbaejahgfbbgbjagbddfgdiaigdadhcfcj"
It throws error:
java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
at line: if (ransomChar.get(i).equals(magazineChar.get(j)))
CodePudding user response：
On each iteration of this loop:
for (int i = 0; i < ransomChar.size(); i ) { boolean flag = false; for (int j = 0; j < magazineChar.size(); j ) { if (ransomChar.get(i).equals(magazineChar.get(j))) { ransomChar.remove(i); magazineChar.remove(j); flag = true; } else if (ransomChar.isEmpty()) { return true; } } if (!flag) { return false; } }
, you know that i is initially less than ransomChar.size(), so that it is safe to perform ransomChar.get(i).
However, the inner loop may remove one (or more!) elements of ransomChar, after which it may no longer be true that i is less than ransomChar.size(). The inner loop continues to iterate, and as a result, it can attempt to retrieve an element of ransomChar that does not exist.
Honestly, the code overall is a mess. Other than this specific issue,
I see no need why you need special cases for all the variations on sizes of note and magazine. I think you might write better code for this if you devoted some effort to designing an approach that just works correctly for all cases.
you are not making good use of the available features of the classes you are using
you are not making good use of general Java language features that would be applicable.
For example, I might write that particular loop as:
for (Character c : ransomChar) {
if (!magazineChar.remove(c)) {
return false;
}
}
return true;
And that's before we come to the fact that you've chosen a suboptimal algorithm. Its execution time will scale as note size * magazine size, whereas there are alternatives that will scale as note size magazine size, instead. That may in fact be important, because choice of an efficient algorithm is one thing that the test cases for coding challenges such as this often try to detect.
CodePudding user response：
Here's a simple way to attack your problem by building a set of candidate characters from magazine. Once you've done that, you just iterate over the ransomNote, checking the set for each character. If you find it, you remove it from the set. If you don't, then you return false. If you make it all the way through, you return true. You need to use a MultiSet because you need to be able to represent multiple copies of the same character in the magazine.
Here's how to do that:
public static boolean canConstruct(String ransomNote, String magazine) {
MultiSet<Character> magazineChars = new HashMultiSet<>();
for (int i = 0; i < magazine.length(); i )
magazineChars.add(magazine.charAt(i));
for (int i = 0 ; i < ransomNote.length(); i ) {
Character c = ransomNote.charAt(i);
if (magazineChars.contains(c))
magazineChars.remove(c);
else
return false;
}
return true;
}
CodePudding user response：
Please find small and simple solution with Time complexity O(n) and Space complexity O(256) or O(1)
int[] count = new int[256];
for (char c : magazine.toCharArray()) {
count[c] ;
}
for (char c : ransomNote.toCharArray()) {
if (count[c]-- == 0) return false;
}
return true;
