java - 递归拼出一个词

Question

我得到了这个:

Write a recursive program that, given a string with no spaces in it, breaks it into every possible segmentation of the string into "words". That is, print out every possible version of the string with spaces inserted in it. The order in which the segmented strings are given does not matter, but all possible segmentations must be given, with no repeats.

如果有人可以提供帮助，我什至完全不知道如何开始。

输出应该是这样的:

 Enter a string: ABCD

 ABCD
 A BCD
 A B CD
 A B C D
 A BC D
 AB CD
 AB C D
 ABC D

Answer 1

我会给你一些提示来帮助你:

想想如何递归解决这个问题。基本上，这可以通过“分而治之”的变体来解决。对于给定的长度为 n 的字符串，有 n-1 处可以插入分隔符。

因此，如果您有一个长度为 2 的字符串，您可以在一个地方插入分隔符，并且有两种变体:插入分隔符或不插入分隔符。

如果你有一个长度为 3 的字符串，你在 2 个地方有 2 个选择。因此，该函数可以创建一个首先插入空格的字符串，并使用字符串的未处理尾部递归调用自身以生成该子字符串的所有变体。然后在一开始没有插入空格的地方创建另一个前缀字符串，然后用字符串的其余部分再次调用自身。

对于每个递归调用，它需要将已经生成的字符串前缀和剩余未处理的字符串尾部传递给自己。