java - 生成字符串所有分区的递归方法

Question

我正在尝试通过 String 的 partitioning 来解决这个问题。我们以“abc”为例。
有 4 个分区 - {a,bc}, {ab,c}, {abc}, {a,b,c}。
我正在尝试编写一个 recursive 方法来生成 partitions 到 Lists 的 ArrayList 但我很难做到所以。将不胜感激!

static List<List<String>> partitions = new ArrayList<>();
static List<String> partition = new ArrayList<>();

static void recurse(int size, String str) {
    if (str.length() <= size) {
        return;
    }
    partition.add(str.substring(0, size));
    for (int i = 1; i < str.length(); i++) {
        if (size < str.length())
            recurse(i, str.substring(size));
    }
    partitions.add(partition);
}

现在当我调用这个方法时它输出

[[, a, b, ab], [, a, b, ab], [, a, b, ab], [, a, b, ab]]

代替 [[a, b, c], [a, bc], [ab, c], [abc]]

，所以我一定是做错了什么:

recurse(0, "abc");
    System.out.println(partitions.toString());

Answer 1

我认为使用全局变量不是一个好主意。

递归函数可能会返回分区列表。

所以，考虑函数的输入和输出

示例:

"ABC"

func("ABC") => func("BC") => func("C")

func("C") 返回 [["C"]]

所以你可以在“C”前面附加“B”或者创建一个分区。

func("BC") 返回 [["BC"], ["B", "C"]]

然后用"A"

再次做上面的事情

func("ABC") 返回 [["ABC"], ["A", "BC"], ["AB", "C"], ["ABC"]]

代码:

static List<List<String>> recursive(String str) {
    List<List<String>> result = new ArrayList<>();

    if (str.length() == 1) {
        result.add(new ArrayList<>());
        result.get(0).add(str);
        return result;
    }

    for (List<String> list : recursive(str.substring(1))) {
        List<String> append = new ArrayList<>(list);
        append.set(0, str.substring(0, 1) + append.get(0));
        List<String> add = new ArrayList<>(list);
        add.add(0, str.substring(0, 1));
        result.add(append);
        result.add(add);
    }
    return result;
}

添加:

另外，您的代码只创建了一次partition。所以 partitions 中的 partition 来自相同的引用!

因此，添加或编辑一个分区会影响每个分区。

因此，如您所见，所有分区都是相同的。

由于这些原因，您最好每一步都创建新的ArrayList，而不是使用全局变量。