private static boolean isValidWord(String word, boolean isOriginal, HashMap<String, Boolean> map) {
        if (!isOriginal && map.containsKey(word)) {
            return map.get(word);
        }
        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) == true &&
                isValidWord(right, false, map)) {
                return true;
            }
        }
        map.put(word, false);
        return false;
    }