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