java中一個句子中所有子字符串的組合

Question

我需要在空格分隔的字符串中找到單詞的組合。假設字符串爲「我會去」，那麼輸出將是 -

1. 我，會，走
2. 我，會去
3. 我，去

字符串可能更大。 我試過但卡住了。你能幫我解決這個問題嗎？ 在此先感謝。

public class Combination_Of_Words_In_Sentence { 

public static void main(String[] args) { 
    String inputString = "I will go"; 
    String[] arrString = inputString.split(" "); 
    printString(arrString); 
} 

private static void printString(String[] arrString) { 
    int len = arrString.length; 
    String[] arr = new String[len]; 

    for(int i=0;i<arrString.length;i++){ 
     for(int j=0;j<i+1;j++){ 
      arr[i] = arrString[j]+" "; 
      System.out.println(); 
     } 
     arr[i] +=","; 
     printPatternUtil(arrString, arr, 1, 1, len); 
    } 
} 

private static void printPatternUtil(String[] arrString, String[] arr, 
     int i, int j, int n) { 
    if(i == n){ 
     // arr[j] = " "; 
     for(int k=0;k<arr.length;k++) 
     System.out.print(arr[k]); 

     System.out.println(); 
      return; 
    } 
    arr[j] = arrString[i]+","; 
    printPatternUtil(arrString, arr, i+1, j+1, n) ; 

    // Or put a space followed by next character 
    // arr[j] = ","; 
    //arr[j+1] = arrString[i]+ " "; 

    // printPatternUtil(arrString, arr, i+1, j+2, n); 

} 

} 

Answer 1

我想建議您使用按位解決方案，以避免需要遞歸。 您可以用二進制數來計算您需要的組合數。例如，用兩個單詞，你需要一個逗號。 用三個字，你需要兩個逗號。 所以，逗號數量=字數-1。

我們可以用計數器中的位來表示逗號。

• 第一個逗號= 0位
• 第二個逗號= 1位
• 三逗號=第2位
• 等...

因此，對於兩個逗號，我們需要2位。 與2個比特的可能組合是：

• 0B00 = 0
• 0B01 = 1
• 0b10 = 2
• 0b11 = 3

三年逗號，則可能的組合是0b000 = 0,0b001 = 1,0b010 = 2,0b011 = 3,0b100 = 4,0b101 = 5,0b110 = 6,0b111 = 7

因此，對於兩個通信因爲您只需從0（0b00）到3（0b11）進行計數並測試每一位以查看是否需要插入逗號。對於三個逗號，計數從0（0b000）到7（0b111）。

這很容易計算。對於2個逗號，採取2的權力2 = 4.對於3個逗號，採取2的權力3 = 8。

String[] words = {...}; 
int wordcount = words.length; 
int commacount = wordcount - 1; 
// Calculate the highest number to count to, in our loop 
int looplimit = 1 << commacount; // Same as 2 to the power commacount; 
for(int i=0;i<looplimit;i++) 
{ 
    // Start this phrase version with the first word. 
    String result = words[0]; 

    // Add the rest of the words, optionally adding commas. 
    // We've already added a word, so only count to wordcount-1 
    for(int j = 0; j<wordcount-1;j++) 
    { 
     // For word j, test the loop counter (i) to see if bit j is set. 
     boolean needComma = (i & (1 << j)) != 0; 

     // Add a comma or a space to this phrase version 
     result += needComma ? "," : " "; 

     // Add this word to the phrase version 
     result += words[j+1]; 
    } 
    System.out.println(result); 
}