遞歸？字符串中的組合

Question

我一直在處理以下遞歸問題一段時間，但一直未能弄清楚。基本上，你有某種由某些詞組成的句子，其中所有詞彙只是卡在一起，沒有間隔。這個想法是找出可用於創建句子的所有可能的單詞組合的數量。

例如，

• 單詞：OOK，ookook
• 句子：ookookook
• 解決方案：{OOK，OOK，OOK}，{ookook，OOK}，{OOK，ookook}。

又如：

• 單詞：OOGA，oogam，oogum，莫克，OOK
• 句子：oogamookoogumook
• 解決方案：{OOGA，莫克，oogum，OOK}，{oogam， OOK，oogum，OOK}

我已經嘗試了很多東西，終於放棄，努力做手工......

public static int WAYS(String word) { 
    int ways = 1; 
    for (int i = 0; i < word.length(); i++) { 
     try{ 
      if(word.substring(i, i - 2).equals("ug")){ 
       if(word.substring(i - 4, i - 2).equals("ug")){ 
        ways++; 
       } 
      } 
      else if(word.substring(i, i - 3).contains("ook")){ 
       System.out.println(word.substring(i-6, i-3)); 
       if(word.substring(i - 6, i - 3).equals("ook")){ 
        ways++; 
       } 
       if(word.charAt(i - 4) == 'm'){ 
        if(word.substring(i - 8, i - 4).equals("ooga") || word.substring(i - 8, i - 4).equals("oogu")){ 
         ways++; 
        } 
       } 
      } 
      else if(word.substring(i, i - 4).contains("mook")){ 
       if(word.substring(i - 8, i - 4).contains("mook")){ 
        ways++; 
       } 
      } 
      if(word.substring(i, i - 2).equals("oog")){ 
       if(word.charAt(i + 2) == 'm'){ 
        if(word.charAt(i + 1) == 'a' || word.charAt(i + 1) == 'u'){ 
         ways++; 
        } 
       } 
      } 
     } catch(Exception e){ 
      continue; 
     } 
    } 
    return ways; 
} 

但它沒有奏效。有人請給我一個想法或使用遞歸來解決這個問題的例子嗎？

Answer 1

1）正確命名您的方法，「WAYS」是一個常量名稱，而不是方法名稱。

2）提供可運行代碼，特別是在代碼太短的情況下。

3）不要對控制流使用異常。

4）你在你的代碼中使用了像「uug」和「ook」這樣的魔法值嗎？這看起來簡單明瞭嗎？這看起來可以維持嗎？如果你有一百萬個不同詞彙的詞彙，這應該是什麼樣子？

編輯：給出完整的清單有點無聊，所以我留下了一些空白。嘗試填補這些，希望有所幫助。

public class JammedWords { 
    public static int ways(String sentence, String[] words) { 
    if (sentence.isEmpty()) { 
     // The trivial case: the sentence is empty. Return a single number. 
    } else { 
     int c = 0; 
     for (String w: words) { 
     if (sentence.startsWith(w)) { 
      // call method recursively, update counter `c`. 
     } 
     } 
     return c; 
    } 
    } 
    public static void main(String[] args) { 
    System.out.println(ways("ookookook", new String[]{"ook", "ookook"})); 
    System.out.println(ways("oogamookoogumook", new String[]{"ooga","oogam","oogum","mook","ook"})); 
    } 
} 

提示：

A）理解空集之間的差值，設置含有空集，包含含有一個空集等，其包含空集是當然不是空集的一組設置，並且它們的大小不爲0.

B）有一個方便的方法String.substring（n），它會刪除第n個字符之前的所有內容。還有String.length（）來獲取單詞的大小。

Answer 2

希望VB.NET代碼不會介意，只是爲了把握。

Private Sub Go() 
    Dim words As New List(Of String) 

    words.Add("ooga") 
    words.Add("oogam") 
    words.Add("oogum") 
    words.Add("mook") 
    words.Add("ook") 

    Search("oogamookoogumook", words, "", New List(Of String)) 
End Sub 

Private Sub Search(ByVal sentence As String, _ 
         ByVal wordList As List(Of String), _ 
         ByVal actualSentenceBuildingState As String, _ 
         ByVal currentPath As List(Of String)) 

    For Each word As String In wordList 
     Dim actualSentenceAttemp As String 
     Dim thisPath As New List(Of String)(currentPath) 

     thisPath.Add(word) 
     actualSentenceAttemp = actualSentenceBuildingState + word 

     If actualSentenceAttemp = sentence Then 
      Debug.Print("Found: " + String.Join("->", thisPath.ToArray())) 
     End If 

     If actualSentenceAttemp.Length < sentence.Length Then 'if we are not too far, we can continue 
      Search(sentence, wordList, actualSentenceAttemp, thisPath) 
     End If 
    Next 
End Sub 

打印輸出：

Sentence: oogamookoogumook 
Found: ooga->mook->oogum->ook 
Found: oogam->ook->oogum->ook 

Sentence: ookookook 
Found: ook->ook->ook 
Found: ook->ookook 
Found: ookook->ook 

想想它作爲走在曲線圖（其無非其實其他人）。你從零開始（空字符串）。現在你開始迭代地將單詞列表中的單詞添加到你的'當前正在嘗試的句子'中。在向當前的attemptp添加單詞之後，您只能以三種可能的狀態結束：（1）您獲得了最後一個句子，（2）當前attemptp比目標句短，因此仍然適合添加下一個單詞（遞歸調用），或3），你當前的嘗試比目標序列更長（或者長度相同但不相等），因此繼續搜索它是沒有意義的。

你必須記住的是路徑 - 「我怎麼到這裏來的？」列表（回溯）。