java - 递归回溯以创建给定字符串的排列

Question

我目前正在处理用户输入单词的编程任务

即“那个”

并且程序应该返回可以从给定字符串中生成的所有有效单词

即[那个，帽子，在]

我遇到的问题是应该使用检查前缀是否有效的递归方法来创建生成的单词。

即如果给定的单词是“kevin”，一旦程序尝试组合“kv”，它应该知道没有单词以kv开头并尝试下一个组合以节省时间。

目前，我的代码只创建所有排列，当输入大于 8 个字母时，这需要相对大量的时间。

protected static String wordCreator(String prefix, String letters) {
    int length = letters.length();

        //if each character has been used, return the current permutation of the letters
        if (length == 0) {
            return prefix;
        }
        //else recursively call on itself to permute possible combinations by incrementing the letters
        else {
            for (int i = 0; i < length; i++) {
                words.add(wordCreator(prefix + letters.charAt(i), letters.substring(0, i) + letters.substring(i+1, length)));
            }
        }
        return prefix;
    }

如果有人可以帮助我解决这个问题，我将不胜感激。我还使用 AVL 树来存储字典单词以进行必要的验证。