java - 构建所有字符串，其中每个数字都是一组字符

Question

这个问题已经有答案了:

Return the cross product of a list of lists (4 个回答)

已关闭 3 年前。

如果我有一个二维字符字符串数组

{{"A", "B", "C"},{"D", "E", F"} ... {"P", "Q", "R"}, {"S", "T", "W"}}

那么我如何构建一个具有主数组长度的字符串，并且每个数字都是内部数组中的一个字符？例如，输出为

"ADG...PS", "ADG...PT, "ADG...PW", "ADG...QS" ... 。

要在没有递归的情况下完成此操作，我需要 n嵌套 for 循环，其中 n是主数组的长度。但是我无法对其进行硬编码。

我认为基本情况是最后一个字符串，例如 C, F, ..., R, S你将从 "ADG...PS" 开始，并以某种方式增加它，但我不知道如何实现它。我知道在 python 中有一个库可以做到这一点，但我需要在 java 中做到这一点。

Answer 1

递归确实是答案，但不是结果集中的字符串之间的递归，而是沿着结果字符串中的字符的递归。

用不太抽象的方式来说:所有长度为 n 的结果字符串都可以通过获取长度为 n-1 的结果字符串并附加可能的最后一个字符来形成。

在代码中:

List<String> generateStrings(String[][] possibleCharacters, int index) {
    if (index < 0) {
        return new ArrayList<>("");
    } else {
        var results = new ArrayList<String>();
        for (var s : generateStrings(possibleCharacters, index - 1)) {
            for (var c : possibleCharacters[index]) {
                results.add(s + c);
            }
        }
        return results;
    }
}

效率纯粹主义者会对重复的字符串连接感到不满。为了避免这种情况，我们可以使用单个 StringBuilder构建所有字符串:

void generateStrings(String[][] possibleCharacters, StringBuilder prefix, List<String> results) {
    var index = prefix.length();
    if (index == possibleCharacters.length) {
        results.add(prefix.toString());
    } else {
        for (String c : possibleCharacters[index]) {
          prefix.append(c);
          generateStrings(possibleCharacters, prefix, results);
          prefix.delete(index, prefix.length());
        }
    }
}

另一个可能的问题是生成的字符串列表变得非常大非常快，因此在处理它们之前将它们全部存储在内存中可能被认为是浪费。在 phython 中，您可以使用生成器来实现这一点。在 Java 中，最接近的语义等效项是 Stream ，但它们很难提供，因此简单的回调可能是更好的选择。也就是说，而不是传递 List<String>要接收结果，您需要传递 Consumer<String>每个结果都会调用它。