Validate whether a ransom note can be made from a dictionary of words

Question

For simplicity, it is checking whether the characters in a string (that needs to be created) are present in a larger string (dictionary). Would a character array of the letters make sense here, or would it be better with a Map<Character, Integer>?

public class RansomNoteProblem {
public static void main (String args[]){

    String blob = "thisisanothwllowllqend";
    String note = "thisisanotex";

    System.out.println(validateLetterCreation(blob,note));
}

public static boolean validateLetterCreation(String dict, String note){
    int charArray[] = new int[256];
    for(int i=0;i<dict.length();i++){
        int charValue = (int)dict.charAt(i);
        charArray[charValue]++;
    }

    for(int i=0;i<note.length();i++){
        int charValue = note.charAt(i);
        if(charArray[charValue]<=0){
            return false;
        }
        else {
            charArray[charValue]--;
        }
    }
    return true;

}
}

Answer 1

Algorithm

You build an array with the counts of letters in the newspaper. Then you iterate over the letters of the ransom note, and short circuit when a letter is missing (count goes below zero).

Can this be done the other way around? That is, build an array of counts from the note, then iterate over the newspaper and short circuit when the letter is completed. Yes that would work too, but using a map of counts instead of an array, deleting letters that were completed, and an empty map marking the ransom note competed.

So which way is better? Consider these questions:

• Which tends to be bigger: the ransom note or the newspaper? To complete the task of making the ransom note, which one must be inevitably finite, and which one may be infinite, the ransom note or the newspaper?
• What if the newspaper contains billions of letters?
• What if you receive the available letters (of the newspaper) as a (possibly infinite) stream of characters?
• How would you make a ransom note in real life? Cut out letter by letter from a newspaper and build neat little stacks, ready for the ransom note? Probably not ;-)

Naming

The name validateSomething sounds like it might throw an exception is invalid, or mutate state (return void). More common prefixes for boolean methods are "is", "has" and "can". In this example, instead of validateLetterCreation, I would recommend canCreateRansomNote.

The name charArray is misleading. A reader might think it's an array of characters. When it's actually counts of letters, so I would call it just like that: countsOfLetters.

Testing

One example case with a sample newspaper and a sample ransom note executed in a main method is far from enough to verify the correctness of such program. Consider looking into a proper unit testing framework, such as JUnit.

Answer 2

Coding conventions

You should have a space before and after a binary operator:

int i = 0;

not

int i=0;

What comes to declaring arrays, you should have

String[] args

instead of

String args[]

Algorithm

You can simplify the algorithm a bit:

import java.util.HashMap;
import java.util.Map;

public class RansomNoteProblem {

    public static void main(String args[]) {
        String blob = "thisisanothwllowllqend";
        String note = "thisisanotex";

        System.out.println(validateLetterCreation(blob, note));
    }

    public static boolean validateLetterCreation(String dict, String note) {
        final Map<Character, Integer> map = new HashMap<>();

        for (final char c : dict.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (final char c : note.toCharArray()) {
            if (map.getOrDefault(c, 0) == 0) {
                return false;
            }

            map.put(c, map.get(c) - 1);
        }

        return true;
    }
}

Hope that helps.