递归字符串函数 (Java)

Question

我正在尝试设计一个基本上执行以下操作的函数：

String s = "BLAH";

将以下内容存储到数组中： 废话 拉 呸 BLH 布拉 BL 巴 巴赫 啊 所以

基本上我所做的就是一次减去其中的每个字母。然后一次减去两个字母的组合，直到剩下 2 个字符。将每一代存储在一个数组中。

希望这是有道理的，

杰克

Answer 1

你是怎么得到“al”的？这些也混在一起了吗？

我将创建一个 HashSet 来保存所有排列并将其传递给递归方法。

void foo(HastSet<String> set, String string) {
    if (string.length < 2) // base case
        return
    else {
        // add the string to the hashset
        set.add(string);

        // go through each character
        for (int i = 0; i < string.length; i++) {
            String newString = s.substring(0,i)+s.substring(i+1);
            foo(set, newString);
        }
    }
}

如果你关心独特性的话。如果没有，您可以使用向量。无论哪种方式，您都可以使用 toArray 来取回数组。

Answer 2

这是@voodoogiant 答案的优化。基本上我想推迟单词构建任务直到递归的基本情况。这样您就可以使用 StringBuilder 来构建单词。因此，基本上递归所做的就是打开和关闭布尔数组的位，这些位表示某个字母是否必须在下一个单词中使用。

有一段时间没有写java代码了，所以如果有些东西不能编译，请原谅我。

void buildWords(String baseWord, boolean[] usedLetters, HashSet<String> words, int index){
    if (index == baseWord.length()){
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < index; i++){
            if (usedLetters[i])
                builder.append(baseWord.characterAt(i));
        }
        words.add(builder.toString());
    }
    else{
        usedLetters[index] = true;
        buildWords(baseWord, usedLetters, words, index+1);
        usedLetters[index] = false;
        buildWords(baseWord, usedLetters, words, index+1);
    }
}

您必须注意的事情：

1. 这可以构建空字符串（如果数组的所有位置均为 false）。
2. 这可以构建重复的单词（如果baseWord有连续的重复字符），并且我不记得HashSet在添加重复键时是否抛出异常。
3. 不记得将字符附加到末尾的 StringBuilder 方法是否称为“append”，但您明白了。
4. 不记得输出构建的字符串的 StringBuilder 方法是否是“toString”，但您也明白了。

Answer 3

您实际上并不需要递归来执行此操作。这是一个迭代算法：

    String master = "abcd";
    final int L = master.length();

    List<String> list = new ArrayList<String>();
    list.add(master);
    Set<String> current = new HashSet<String>(list);
    for (int i = L-1; i >= 2; i--) {
        Set<String> next = new HashSet<String>();
        for (String s : current) {
            for (int k = 0; k < s.length(); k++) {
                next.add(s.substring(0, k) + s.substring(k + 1));
            }
        }
        list.addAll(current = next);
    }
    System.out.println(list);
    // prints "[abcd, abc, abd, bcd, acd, ac, ad, ab, bc, bd, cd]"

这本质上是一个广度优先搜索。您从最初包含String master的当前集开始。然后，在 i 的每次迭代中，您都会遍历 for (String s : current) 并生成 next 集合，这是通过删除每个来自 s 的可能字符。

Effective Java 第 2 版：第 25 条：优先使用列表而不是数组，但如果您坚持使用 String[] 存储，则可以在最后执行以下操作。

    String[] arr = list.toArray(new String[0]);

另请参阅

• 用列表数据填充数组