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:
- A couple of questions nested inside the codes regarding premature optimization.
- 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"));
}
}