Given set of cubes can we get a given word?

Question

Given some cubes, can cubes be arranged such that an input word can be formed from the top view of the cubes?

For example: assume an imaginary cube with only 3 surfaces where cube1: {a, b, c} and cube2 {m, n, o}, then word an can be formed but word ap cannot be formed.

Please look into the two following issues:

1. A couple of questions nested inside the codes regarding premature optimization.
2. Verifying complexity to be O(n!), where n is the number of alphabets in the word.

public final class CubeFind {
    private CubeFind() {}

    public static boolean checkWord(char[][] cubeMatrix, String word) {

        /*
         * Premature optimization: read that they were bad practices. they look good in my code, should i keep them ? 
         * 
         * 1. If not checked now, then NPE would result after hashMap is computed. on line 46 
         * if (cubeMatrix == null) { throw new NullPointerException("The input cube matrix should not be null");
         * 
         * 2. if (word == null {throw new NullPointerException("The input word should not be null"); }
         * 
         * 3. if (cubeMatrix.length != word.length()) return false;
         */

        char[] chWords = word.toCharArray();
        final Map<Character, Integer> charFreq = new HashMap<Character, Integer>();

        for (char ch : chWords) {
            if (charFreq.containsKey(ch)) {
                charFreq.put(ch, charFreq.get(ch) + 1);
            } else {
                charFreq.put(ch,  1);
            }
        }

        return findWordExists(cubeMatrix, charFreq, 0);
    }

    private static boolean findWordExists (char[][] cubeMatrix, Map<Character, Integer> charFreq, int cubeNumber) {
        assert charFreq != null;

        if (cubeNumber == cubeMatrix.length) {
            for (Integer frequency : charFreq.values()) {
                if (frequency > 0) return false;
            }
            return true;
        }

        for (int i = 0; i <  cubeMatrix[cubeNumber].length; i++) {
            if (charFreq.containsKey(cubeMatrix[cubeNumber][i])) {
                int frequency = charFreq.get(cubeMatrix[cubeNumber][i]);
                // this check is needed to get a false result when input chars are less than number of cubes
                // eg: 'hel' should return false.
                if (frequency > 0) {
                    charFreq.put(cubeMatrix[cubeNumber][i], frequency - 1);
                    if (findWordExists(cubeMatrix, charFreq, cubeNumber + 1)) {
                        return true;
                    }
                    charFreq.put(cubeMatrix[cubeNumber][i], frequency);
                }
            }
        }

        return false;
    }


    public static void main(String[] args) {
        char[][] m = {{'e', 'a', 'l'} , {'x', 'h' , 'y'},  {'p' , 'q', 'l'}, {'l', 'h', 'e'}};
        System.out.println("Expected true,  Actual: " + CubeFind.checkWord(m, "hell"));
        System.out.println("Expected true,  Actual: " + CubeFind.checkWord(m, "help"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hplp"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hplp"));
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "helll")); 
        System.out.println("Expected false, Actual: " + CubeFind.checkWord(m, "hel")); 
    }
}

Answer 1

Verify complexity to be O(n!), where n is the number of alphabets in the word.

Indeed.

    private CubeFind() {}

You don't need this to get a default constructor.

Premature optimization: read that they were bad practices. they look good in my code, should i keep them ?

If not checked now, then NPE would result after hashMap is computed. on line 46

1. if (cubeMatrix == null) { throw new NullPointerException("The input cube matrix should not be null");

2. if (word == null {throw new NullPointerException("The input word should not be null"); }

Please don't do that! You're not gaining anything, the first reason being that it's going to fail very quickly if you really get null or word. The second reason is that there's no reason to get null here, why would that happen? You're simply calling this function from main, it cannot be null. When not for useless optimizations, this practice is called defensive programming and is only useful in a few specific scenarios.

 if (cubeMatrix.length != word.length()) return false;

This one can also be seen as a way to eliminate cases you don't want to reason about later on. That is, you know after this line that you will have the correct number of cubes, and it simplifies the reasoning and the code. You should keep it.

if (cubeNumber == cubeMatrix.length) {

This one wasn't obvious at first, and could deserve a comment, eg. "If we chose a letter for all cubes, check that no letter is left", maybe.

charFreq.put(cubeMatrix[cubeNumber][i], frequency - 1);
if (findWordExists(cubeMatrix, charFreq, cubeNumber + 1)) {
    return true;
}
charFreq.put(cubeMatrix[cubeNumber][i], frequency);

Nice trick. Another way to do it is to give a copy of cubeMatrix. You would then avoid the second put, but it could be very costly here due to the number of copies you would have to do: don't do it.

I would define premature optimization as "a change made for performance reasons that brings no benefit or degrades readability, and has not been proved to actually improve performance".

Last, your tests are okay for this usage, but consider using an unit test library like JUnit to manage tests, this will help you later on.