java – 递归地拼出一个单词

发布时间：2020-12-15 04:54:22 所属栏目：Java 来源：网络整理

导读：我得到了这个： 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. T

我得到了这个：

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

解决方法

我会给你提示帮助：

想想如何递归地解决这个问题.基本上,这可以通过“分而治之”的变化来解决.对于给定长度为n的字符串,有n-1个位置可以插入分隔符空格.

因此,如果您有一个长度为2的字符串,则有一个位置可以插入分隔符,还有两个变体：是否插入分隔符.

如果您有一个长度为3的字符串,则您在2个位置有2个选项.因此,该函数可以创建一个首先插入空格的字符串,并使用字符串的未处理尾部递归调用自身,以生成该子字符串的所有变体.然后创建另一个前缀字符串,其中第一个位置没有插入空格,并再次使用字符串的其余部分调用自身.

对于每个递归调用,它需要传递已经生成的字符串前缀以及字符串的剩余未处理尾部.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!