Java - 使用递归从字符串创建所有子字符串

Question

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

Answer 1

这个问题有重叠的子问题,因为你做的那样自上而下的递归效果不是很好.您正在多次评估多个子字符串.

实际上它非常无效(我猜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循环作为练习;)

Answer 2

以下证明是最佳解决方案:

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