java递归方法生成字符串的所有分区
我试图用String
的partitioning
来解决这个问题。让我们以“abc”为例
有4个partitions
-{a,bc}, {ab,c}, {abc}, {a,b,c}.
我正试图编写一个recursive
方法来生成partitions
到ArrayList
{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());
# 1 楼答案
我认为使用全局变量不是个好主意
递归函数可以返回分区列表
所以,考虑函数的输入和输出
示例:
func("ABC") => func("BC") => func("C")
func("C") returns [["C"]]
因此,您可以在“C”前面附加“B”,或者创建一个分区
func("BC") returns [["BC"], ["B", "C"]]
然后用“A”
func("ABC") returns [["ABC"], ["A", "BC"], ["AB", "C"], ["ABC"]]
代码:
添加:
此外,您的代码只创建一次
partition
。所以partitions
中的partition
来自同一个引用因此,添加或编辑
partition
会影响每一个partition
如你所见,所有的
partition
都是一样的由于这些原因,您最好在每个步骤中创建新的
ArrayList
,而不是使用全局变量# 2 楼答案
另一种选择是,如果您更喜欢使用Java 8流,而不是传统的迭代:
例如,
partitions("abcde").forEach(System.out::println)
将打印字符串的所有分区如果要转换回列表,则:
如果您不熟悉streams,
else
子句可以解释为:对于介于1和字符串长度(包括1)之间的所有数字,将该数字的子字符串的所有分区向前流,然后在每个项的开头插入该数字的子字符串