Java - 使用递归从字符串创建所有子字符串
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18280442/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java - using recursion to create all substrings from a string
提问by davidjhp
The following code in Java uses recursion to create all possible substrings from a string. I am wondering is there a better way of coding this? I want to use recursion.
以下 Java 代码使用递归从字符串创建所有可能的子字符串。我想知道有没有更好的编码方法？我想使用递归。
public class main {
public static void main(String[] args) {
generate("hello");
}
public static void generate(String word) {
if (word.length() == 1) {
System.out.println(word);
return;
}else{
System.out.println(word);
generate(word.substring(0, word.length()-1));
generate(word.substring(1, word.length()));
}
}
}
FAQ Q - Why do I want to do this using recursion? A - Because the CEO of StackOverflow says recursion is important http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
常见问题 Q - 为什么我要使用递归来做到这一点？A - 因为 StackOverflow 的 CEO 说递归很重要 http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
采纳答案by davidjhp
The following turned out to be the best solution:
事实证明，以下是最好的解决方案：
public class recursive {
static String in = "1234";
public static void main(String[] args) {
substrings(0,1);
}
static void substrings(int start, int end){
if(start == in.length() && end == in.length()){
return;
}else{
if(end == in.length()+1){
substrings(start+1,start+1);
}else{
System.out.println(in.substring(start, end));
substrings(start, end+1);
}
}
}
}
It first checks the base case: if both start and end are equal to in.length(). Because if they are, that means there are no more substrings to be found, and the program ends.
它首先检查基本情况：如果开始和结束都等于 in.length()。因为如果它们是，那就意味着没有更多的子串可以找到，程序就结束了。
Let's start with start=0 and end=1. They obviously don't equal in.length(), and end definitely doesn't equal in.length()+1. Thus, substring(0,1) will be printed out, which is 1. The next iteration of substrings will be substrings(0,2), and in.substring(0,2) will be printed, which is 12. This will continue until end == in.length()+1, which happens when the program finishes substrings(0,4) and tries to move on to substrings(0,5). 5 == in.length()+1, so when that happens, the program will do substrings(start+1,start+1), which is substrings(1,1). The process will continue with substrings(1,2), and (1,3), until (1,5) when the program will run substrings(2,2).
让我们从 start=0 和 end=1 开始。它们显然不等于 in.length()，并且 end 绝对不等于 in.length()+1。因此，将打印出 substring(0,1)，即 1。子串的下一次迭代将是 substrings(0,2)，并且将打印 in.substring(0,2)，即 12。这将继续直到 end == in.length()+1，当程序完成 substrings(0,4) 并尝试移动到 substrings(0,5) 时会发生这种情况。5 == in.length()+1，所以当这种情况发生时，程序会做 substrings(start+1,start+1)，也就是 substrings(1,1)。该过程将继续使用 substrings(1,2) 和 (1,3)，直到程序运行 substrings(2,2) 直到 (1,5)。
All of this will continue until substrings(4,4), which, at that point, the program stops.
所有这一切都将继续，直到 substrings(4,4)，此时程序停止。
The result looks like this:
结果如下所示：
1 12 123 1234
1 12 123 1234
2 23 234
2 23 234
3 34
3 34
4
4
回答by Honza Brabec
This problem has overlapping subproblems and because of that the top-down recursion as you do is not much effective. You are evaluating multiple substrings multiple times.
这个问题有重叠的子问题，因为你所做的自上而下的递归并不是很有效。您正在多次评估多个子字符串。
Actually it is horribly ineffective (I would guess O(2^n)). Just try to run it on a bit longer string.
实际上它是非常无效的（我猜是 O(2^n)）。尝试在更长的字符串上运行它。
generate("OverlappingSubproblems");
If you are interested in a better way of solving this you can try something like this:
如果您对解决此问题的更好方法感兴趣，可以尝试以下操作：
public static void generate2(String word) {
for (int from = 0; from < word.length(); from++) {
for (int to = from + 1; to <= word.length(); to++) {
System.out.println(word.substring(from, to));
}
}
}
If you want to use recursion you can try to rewrite the for-loops with recursion as exercise ;)
如果你想使用递归，你可以尝试用递归重写for循环作为练习;)
回答by Jason C
There is a lot to be learned from Honza's answer.I suggest you try and rewrite that as a recursive algorithm.
从 Honza 的回答中可以学到很多东西。我建议您尝试将其重写为递归算法。
As with any recursive approach, divide it into self-referencing subproblems:
与任何递归方法一样，将其划分为自引用子问题：
1. substrings(X) = substrings_starting_at_first_character(X) + substrings(X minus first char).
2. substrings_starting_at_first_character(X) = X + substrings_starting_at_first_character(X minus last char).
Next figure out your non-self-referencing base cases:
接下来找出您的非自引用基本情况：
1. substrings("") = empty set.
2. substrings_starting_at_first_character("") = empty set.
And go from there.
从那里去。
回答by Anshu
Another clean approach - using both looping and recursion (and does not have overlapping problem)
另一种干净的方法 - 使用循环和递归（并且没有重叠问题）
public static void printCombinations(String initial, String combined) {
System.out.print(combined + " ");
for (int i = 0; i < initial.length(); i++) {
printCombinations(initial.substring(i + 1),
combined + initial.charAt(i));
}
}
public static void main(String[] args) {
printCombinations("12345", "");
}
And output is - 1 12 123 1234 12345 1235 124 1245 125 13 134 1345 135 14 145 15 2 23 234 2345 235 24 245 25 3 34 345 35 4 45 5
并且输出是 - 1 12 123 1234 12345 1235 124 1245 125 13 134 1345 135 14 145 15 2 23 234 2345 235 24 245 3 5 3 4 3
回答by SK1
//substring all the words from a string
public class RecSubstring
{
static int c=0;
static void rec(String str)
{
if(str.equals(""))
return;
else
{
c=str.indexOf(' ');
System.out.println(str.substring(0,c));
rec(str.substring(c+1));
}
}
public static void main(String args[])
{
String st="We are Happy"+" " ;
rec(st);
}
}
回答by Ashwini Kumar Maurya
public class SubsequencesOfStr {
public static void main(String[] args) {
String str = "abcd";
System.out.println("0000----" + str.length());
linearCombination(str);
}
static void linearCombination(String str) {
for (int i = 0; i < str.length(); i++) {
int endIndex = i + 1;
for (int j = 0; j < str.length() - i; j++) {
System.out.println(str.substring(j, endIndex));
endIndex++;
}
}
}
}
