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())); 
        }

    }

}

常见问题 问 - 为什么我要使用递归来做到这一点？ A - 因为 StackOverflow 的 CEO 说递归很重要 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循环作为练习；)