递归？字符串中的组合

Question

我一直在处理以下递归问题，但一直没能弄明白。基本上，你有某种由特定单词组成的句子，其中所有单词都挤在一起，而不是间隔开。这个想法是找出可用于创建句子的所有可能单词组合的数量。

例如，

单词：ok, ookook
句子：ookookook
解决方案：{ook, ook, ook}, {ookook, ook}, {ook, ookook}。

另一个例子：

单词：ooga、oogam、oogum、mook、ook
句子：oogamookoogumook
解决方案：{ooga, mook, 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

把它想象成在图表中行走（实际上就是这样）。您从一无所有（空字符串）开始。现在您开始将单词列表中的单词迭代添加到您的 'current attemp for sentence' 中。将单词添加到当前尝试后，您只能以三种可能的状态结束：（1）您得到了最后一句话，（2）当前尝试比目标句子短，因此仍然适合添加下一个单词（递归调用），或（ 3)、你当前的attemp比目标序列长（或等长但不相等），因此继续搜索它没有意义。

你要记住的是路径——"how did i get here?"列表（回溯）。

递归？字符串中的组合

Recursion? Combinations in a String

java

string

recursion

dynamic-programming