如果一個單詞由兩個有效單詞組成

Question

給定一個字典，找出給定單詞是否可以由字典中的兩個單詞組成。例如。給「報紙」，你必須找到它是否可以用兩個字來形成。 （這種情況下的新聞和報紙）。只有我能想到的是從一開始就檢查當前字符串是否是一個單詞。在這種情況下，檢查n，ne，new，news ......如果當前字符串是有效的單詞，則檢查剩餘部分。

另外你如何推廣它的k（意思是說，如果一個詞是由k個詞組成）？有什麼想法嗎？

Answer 1

我首先使用strpos（-like）函數循環遍歷字典，以檢查它是否完全發生。然後嘗試，如果你能找到與結果匹配。 所以它會做這樣的事情：

• 循環遍歷字典strpos-ING的每一個字在字典裏並保存結果到一個數組，假設它給我的結果「新」，「紙」，並'新聞'。
• 檢查是否新增紙張==報紙，檢查是否新增新聞==報紙等，直到您到達紙張+新聞==報紙返回。

雖然不確定它是否是一種好方法，但它似乎比檢查字母的字母（更多迭代）效率更高，而且您沒有解釋如何檢查第二個單詞何時開始。

不知道'你怎麼概括它爲k'是什麼意思。

Answer 2

在中心開始分割可能會使結果更快。例如，對於報紙，您首先會嘗試在'新聞稿'或'newsp aper'上分裂。正如你所看到的，對於這個例子，你會在第一或第二次嘗試中找到你的結果。如果你沒有找到結果，只需向外搜索即可。請參閱下面的「弩」的例子：

cros sbow 
cro ssbow 
cross bow 

Answer 3

對於兩個詞的情況下，這個問題可以通過只考慮單詞分成兩個，然後檢查各佔一半，看它是否是一個所有可能的方式來解決有效的詞。如果輸入字符串的長度爲n，那麼只有O（n）個不同的方式來分割字符串。如果將字符串存儲在支持快速查找的結構中（例如，trie或散列表）。

更有趣的情況是，當你有k> 2個單詞分詞時。爲此，我們可以使用一個非常優雅的遞歸公式：

如果一個單詞可以分成一個單詞，然後可以分成k-1個單詞，那麼它可以分成k個單詞。

遞歸基本情況是，一個單詞可以被拆分爲零字，只要它是空字符串，這是平凡的真實。

要使用此遞歸洞察，我們將修改原始算法，將所有可能的單詞拆分爲兩部分。一旦我們有了分割，我們可以檢查分割的第一部分是否是一個單詞，以及分割的第二部分是否可以分解爲k-1個單詞。作爲一種優化，我們不會考慮所有可能的分裂，而只是針對那些我們知道第一個詞是有效的分裂。下面是用Java編寫的一些示例代碼：

public static boolean isSplittable(String word, int k, Set<String> dictionary) { 
    /* Base case: If the string is empty, we can only split into k words and vice- 
     * versa. 
     */ 
    if (word.isEmpty() || k == 0) 
     return word.isEmpty() && k == 0; 

    /* Generate all possible non-empty splits of the word into two parts, recursing on 
     * problems where the first word is known to be valid. 
     * 
     * This loop is structured so that we always try pulling off at least one letter 
     * from the input string so that we don't try splitting the word into k pieces 
     * of which some are empty. 
     */ 
    for (int i = 1; i <= word.length(); ++i) { 
      String first = word.substring(0, i), last = word.substring(i); 

      if (dictionary.contains(first) && 
       isSplittable(last, k - 1, dictionary) 
       return true; 
    } 

    /* If we're here, then no possible split works in this case and we should signal 
     * that no solution exists. 
     */ 
    return false; 
} 

} 

此代碼，在最壞的情況下，時間爲O（n ^ķ）運行，因爲它試圖生成字符串的所有可能劃分爲k的不同部分。當然，這不太可能發生這種最糟糕的行爲，因爲大多數可能的分裂並不會形成任何單詞。