Java – 使用递归从字符串创建所有子字符串
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())); } } } 常见问题Q – 为什么我要使用递归来做这个？ 答 – 因为StackOverflow的首席执行官说递归很重要http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html
这个问题有重叠的子问题，因为你做的那样自上而下的递归并不是很有效。 您正在多次评估多个子字符串。
实际上它非常无效（我猜是O（2 ^ n））。 只是尝试在更长的字符串上运行它。
generate("OverlappingSubproblems");
如果您对解决此问题的更好方法感兴趣，可以尝试以下方法：
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)); } } }
如果你想使用递归，你可以尝试用递归重写for循环作为练习;）
以下certificate是最佳解决方案：
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); } } } }
它首先检查基本情况：如果start和end都等于in.length（）。 因为如果它们是，那意味着没有更多的子串可以找到，并且程序结束。
让我们从start = 0和end = 1开始。 它们显然不等于in.length（），并且end绝对不等于in.length（）+ 1。 因此，子串（0,1）将被打印出来，即1.子串的下一次迭代将是子串（0,2），并且将打印in.substring（0,2），这将是12。继续直到结束== in.length（）+ 1，这发生在程序完成子串（0,4）并尝试继续到子串（0,5）时。 5 == in.length（）+ 1，所以当发生这种情况时，程序将执行子串（start + 1，start + 1），这是子串（1,1）。 当程序运行子串（2,2）时，该过程将继续使用子串（1,2）和（1,3），直到（1,5）。
所有这一切都将持续到子串（4,4），此时程序停止。
结果如下：
1 12 123 1234
2 23 234
3 34
4
从Honza的答案中可以学到很多东西。我建议你尝试将其重写为递归算法。
与任何递归方法一样，将其划分为自引用子问题：
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).
接下来找出你的非自引用基本情况：
1. substrings("") = empty set. 2. substrings_starting_at_first_character("") = empty set.
从那里开始。
另一个干净的方法 – 使用循环和递归（并没有重叠的问题）
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", ""); }
输出为 - 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
//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); } }