6

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 - 为什么我要使用递归来做到这一点？A - 因为 StackOverflow 的 CEO 说递归很重要 http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

4

10 回答 10

15

这个问题有重叠的子问题，因此你所做的自上而下的递归并不是很有效。您正在多次评估多个子字符串。

实际上它非常无效（我猜是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循环作为练习；）

于 2013-08-16T19:32:56.773 回答
8

以下结果是最好的解决方案：

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)。该过程将继续使用子字符串 (1,2) 和 (1,3)，直到 (1,5) 程序将运行子字符串 (2,2)。

所有这些将一直持续到 substrings(4,4)，此时程序停止。

结果如下所示：

1 12 123 1234

2 23 234

3 34

4

于 2013-08-17T04:42:38.563 回答
1

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

然后从那里走。

于 2013-08-16T19:39:21.353 回答
0

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

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

于 2014-09-22T04:05:39.073 回答
0 
 //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);
  }
 }
于 2018-02-01T16:04:49.040 回答
0 
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++;
   }
  }
 }
}
于 2020-02-16T14:55:54.060 回答
0 
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);
    }
}

}

于 2021-01-20T06:57:50.193 回答
0

使用递归的另一种方法

    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));
        
    }
于 2021-01-30T08:52:52.637 回答
0

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

abc 的输出：a,ab,abc,b,b​​c,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;
}
于 2021-06-25T13:31:54.250 回答
0

这是仅使用 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;
}
于 2021-06-27T05:01:53.017 回答