kogkoge
BAN USERpublic static boolean canMakeWord(String word, char[][] dice) {
HashMap<Character, List<Integer>> diceMap = new HashMap<>();
HashSet<Integer> availableDice = new HashSet<>();
for (int i = 0; i < dice.length; i++) {
for (char c : dice[i]) {
if (!diceMap.containsKey(c))
diceMap.put(c, new ArrayList<>());
diceMap.get(c).add(i);
}
availableDice.add(i);
}
return dfs(word, 0, availableDice, diceMap);
}
private static boolean dfs(String word, int index, HashSet<Integer> availableDice, HashMap<Character, List<Integer>> diceMap) {
if (index == word.length())
return true;
if (!diceMap.containsKey(word.charAt(index)))
return false;
for (int diceIndex : diceMap.get(word.charAt(index))) {
if (availableDice.contains(diceIndex)) {
availableDice.remove(diceIndex);
if (dfs(word, index + 1, availableDice, diceMap))
return true;
availableDice.add(diceIndex);
}
}
return false;
}
- kogkoge April 02, 2019