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

    }

}

常见问题解答 问 - 为什么要使用递归？ 答 - 因为 StackOverflow 的 CEO 表示递归很重要。 http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

- davidjhp

---

你想使用递归，并且你已经有了一个使用递归的可行解决方案？我看不出有什么问题。 - Kayaman

看起来这个递归程序的效率和清晰度都达到了应有的水平。 - ug_

你的方法很好，但我会考虑另一种递归方式。因为你的子字符串是主字符串的单个连续片段，所以你需要处理两个整数变量：起始位置和结束位置。因此，你实际上是在找到它们的组合。例如，对于长度为5的单词“Hello”，你有以下起始/结束位置：1/5、2/5、3/5、4/5、1/4、2/4、3/4等。 - Kon

@Marko，是的，我意识到递归在Java中不太合适，只是想练习递归技能，因为这篇文章http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html - davidjhp

如果你想学习递归，最好的资源是《The Little Schemer》。 - Marko Topolnik

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循环改写成递归练习；）

- Honza Brabec

---

是的，它是n的平方，但另一种解决方案是2的n次方。 - Honza Brabec

啊，我把这两个搞混了。 - rounak

此解决方案未能产生字符串中所有可能的字符组合。 - user3003961

我们正在寻找子字符串而不是组合。 - zad

问题不是要求递归解决方案吗？ - Vyshnav Ramesh Thrissur

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。 因此，将打印出 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)，直到 (1,5) 时，程序将运行 substrings(2,2)。

所有这些都将持续到 substrings(4,4)，在那时，程序停止。

结果如下：

1 12 123 1234

2 23 234

3 34

4

- davidjhp

---

能否详细解释一下你的解决方案的时间和空间复杂度？时间复杂度会是O(nlogn)吗？ - Harshit

当start = end时，该行代码会打印空字符串。它应该只在start != end时执行，类似于if (start != end) { System.out.println(str.substring(start, end)); } - prashant

Answer 3

从 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.

然后从那里开始。

- Jason C

Answer 4

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

- SK1

Answer 5

这里是我的方法，使用2个递归函数pss和pss1来模拟标准O(n^2)解决方案的外部和内部for循环。这一次，我们只是用递归来实现。

对于abc的输出：a，ab，abc，b，bc，c。

// print substrings using recursion

void pss1 ( string s , int i , string op)
{
    // pss1 prints all substrings from a given index
 if(i==s.length()-1)
    {
        op+=s[i];
        cout<<op<<endl;
        return;
    }
     op+=s[i];
     cout<<op<<endl;
     pss1(s,i+1,op);

}
void pss ( string s , int i , string op)
{
    // pss repeats the process of pss1 for all indices by reducing the string size by 1 each time from the front (i.e) abc becomes bc at the 2nd call of psss
    if(s.length()==1)
    {
        cout<<s<<endl;
        return;
    }
    else
    {
            pss1(s,0,op);

        string S=s.substr(1);
        pss(S,0,"");

    }
    return ;
}


int main()
{
    string s;
    cin>>s;
    pss(s,0,"");
    return 0;
}

- Sriram Krishnamurthy

Answer 6

这里是仅使用1个递归函数的工作代码。

这是@davidjhp在c++中解决方案的实现

分析递归问题中的递归堆栈图以了解如何解决给定问题，以产生最终解决方案。

// Print SubStrings using recursion 

void pss(string s, int start, int end)
{
    if(start==s.length()-1)
    {
        cout<<s.substr(start)<<endl;
        return;
    }
    if(end==s.length()+1)
    {
        start++;
        end=start+1;
        pss(s,start,end);
    }
    else if( start<=s.length()&&end<=s.length())
    {
        cout<<s.substr(start,end-start)<<endl;
        pss(s,start,end+1);
    }
}


 int main()
{
 string s;
 cin>>s;
 pss(s,0,1); 
 return 0;
}

- Sriram Krishnamurthy

Answer 7

另一种使用递归的方法

    public static void main(String[] args) 
    {
        subStrings("ABCDE");        
    }
    
    static void subStrings(String str) 
    {
        if(str.length()==0)
        {
            return;
        }
        subString(str);
        subStrings(str.substring(1,str.length()));
        
    }
    
    private static void subString(String str)
    {
        if(str.length()==1)
        {
            System.out.print(str+" ");
            return;
        }
        
        System.out.print(str+" ");
        subString(str.substring(0,str.length()-1));
        
    }
 

- Dhananjay Kansara

Answer 8

void allsubstring(string s,int start,int end)
{
if(start == s.size() &&  end == s.size()) {
    return;
}
else {
    if(end == s.size()) {
        allsubstring(s,start+1,start+1);
    }
    else {
        cout<<s.substr(start,end-start+1)<<endl;
        allsubstring(s,start,end+1);
    }
}

}

- Himanshu Negi

Answer 9

另一种干净的方法 - 同时使用循环和递归（并且没有重叠问题）

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

- Anshu

---

14、15等不是子字符串。你的解决方案会给出使用字符串中字符可以组合出的所有组合…… - Madhusudan

Answer 10

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++;
   }
  }
 }
}

- am-sysout