private static boolean isValidWord(String word, boolean isOriginal, HashMap<String, Integer> map) {
        if (!isOriginal && map.containsKey(word) && map.get(word) > 0) {
            map.put(word, map.get(word) - 1);
            return true;
        }
        for (int i = 1; i < word.length(); ++i) {
            String left = word.substring(0, i);
            String right = word.substring(i);
            if (map.containsKey(left) && map.get(left) > 0) {
                map.put(left, map.get(left) - 1);
                if (isValidWord(right, false, map)) {
                    return true;
                }
                map.put(left, map.get(left) + 1);
            }
        }
        return false;
    }