只是在Java中的一个小递归问题

Question

我目前正在通过一些递归问题的方式工作，我目前停留在一个。

的问题是递归插入空格成一个字符串，为每一个可能的位置，从而使输出看起来是这样的：

Input: ABCD 
Out: 
     ABCD 
     A BCD 
     A B CD 
     A B C D 
     A BC D 
     AB CD 
     AB C D 
     ABC D 

我已经目前对这个问题的工作，并得到了一点多像：

Input: ABCD 
Out: 
     ABCD 
     A BCD 
     A B CD 
     A B C D 

我对这个问题到目前为止的代码：

import java.util.Scanner; 

public class Words 
{ 
    static int counter = 0; 
    static String fString = ""; 
    static String fString2 = ""; 
    static String previous = ""; 
    static String input = ""; 
    static String other = ""; 

    public static String segment(String inputPrefix, String restOfString) 
{ 
    if(restOfString.length() != 0) 
    { 
     if(inputPrefix.equals("")) 
     { 
      fString += restOfString + "\n"; 
      segment(restOfString.substring(0,1), restOfString.substring(1)); 
     } 
     else 
     { 
      previous += inputPrefix + " "; 
      fString += previous + restOfString + "\n"; 
      fString2 = previous + restOfString; 
      segment(restOfString.substring(0,1) 
          , restOfString.substring(1)); 
     } 
    } 
    /*else 
    { 
     counter++; 
     other = fString2.replaceAll(" ", ""); 
     System.out.println(other); 
     if((counter + 1) < other.length()) 
     { 
      System.out.println("Other: " + other); 
      input = other.substring(0, counter + 1); 
      other = other.substring(counter + 1); 
      System.out.println(counter); 
      System.out.println("input: " + input); 
      System.out.print("other: " + other); 

      segment(input, other); 
     } 
     else 
      return fString; 
    }*/ 

    return fString; 

} 

public static void main (String[] args) 
{ 
    Scanner scan = new Scanner(System.in); 
    System.out.print("Enter a string: "); 
    String input = scan.next(); 
    System.out.println(); 
    System.out.println(segment("", input)); 

} 
} 

第二个else子句是我遇到最大麻烦的地方，因为每次我运行un-comment时，它都会进入无限循环。我甚至把int跟踪语句（println语句），它仍然没有帮助。

我已经读了很多遍，它对我来说没有意义，为什么它不起作用。

Answer 1

看起来您已经能够正确进行第一个“分组”，但无法获得下一个分组。

分组为：'A BCD'，'AB CD'和'ABC D'。你需要将你的算法应用到这些分组中的每一个。你已经将它应用到第一个。你如何得到其余的人？

有足够的时间过去了吗？我写了一个python解决方案来看看它与Java相比的样子。

def segment(input, separator=' ', start_from=0): 
    print input 
    # add spaces after each letter starting from start_from index, terminating at last letter-1 
    for i in range(start_from, len(input)-1): 
     # if the next letter is already a space, or this letter is a space, move on 
     if separator in (input[i+1], input[i]): continue 
     # whatever index we're on, do the next one recursively 
     segment(input[:i] + input[i] + separator + input[i+1:], separator=separator, start_from=i+1) 

segment('ABCD') 

Answer 2

让我对代码怀疑的第一件事是，你应该返回一系列字符串，但是你的返回值是一个字符串。

也许，你应该确定你的基本情况和递归步骤。

看起来你已经有了基础案例的开始。您可以在空字符串插入零个空间，所以

allPossibleSpacings("") -> [ "" ] 

，但你不希望在结尾处一个空间，所以你需要一个第二基本情况

allPossibleSpacings("x") -> [ "x" ] 

，然后你的递归一步可能是

allPossibleSpacings("x" + s) -> flatten(
    ∀ t : allPossibleSpacings(s), ["x" + t, "x " + t]) 

我不会帮你写在Java中，因为它的功课，但希望有所帮助。

Answer 3

void recurse(String myString, int start){ 
     System.out.println(myString); 
     for(int i = start; i < myString.length; i++) { 
      if (myString.charAt(i) != ' '){ 
       recurse(myString.Substring(0,i) + ' ' + myString.Substring(i), i+2); 
      } 
     } 
    } 

先用流水调用（“ABCD”，1）;