只是在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）;