給定單詞成爲字典單詞的最小刪除次數

給定一個字典作爲散列表。找到給定單詞所需的最少＃刪除，以使它與字典中的任何單詞匹配。給定單詞成爲字典單詞的最小刪除次數

有沒有一些聰明的技巧來解決這個問題的小於指數複雜度（嘗試所有可能的組合）？

2016-01-20 Weltschmerz

如果單詞可以在字典中 - 0，如果單詞肯定不是在字典中 - 1 –

我不認爲你的問題是有道理的。我猜你正在使用同一個詞：'詞典'表示兩種不同的東西。否則，我不知道你在問什麼。 – JimmyJames

@JimmyJames你有一個包含有效單詞的散列表（查找花費O（1））。程序需要找到某些給定字（String w）所需的最少刪除次數，以便從哈希表中轉換爲一個字。不知道如何更好地解釋。 – Weltschmerz

對於初學者，假設你在散列表中有一個單詞w，並且你的單詞是x。當且僅當w是x的子序列時，可以刪除x中的字母形成w，在這種情況下，需要從x中刪除以形成w的字母數由| x - w |給出。所以肯定有一種選擇是迭代散列表，併爲每個單詞查看x是否是該單詞的子序列，並在表中找到您找到的最佳匹配。

爲了分析這個操作的運行時間，我們假設你的散列表中有n個總字數，並且它們的總長度是L.然後這個操作的運行時間是O（L），因爲你將分別處理所有單詞最多隻有一次。您的初始方法的複雜性是O（| x |＆middot; 2 ^{| x |}），因爲有2 ^{| x |}您可以通過從x中刪除字母來創建可能的單詞，並且您將花費O（| x |）時間處理每個單詞。根據字典的大小和字的大小，一種算法可能比另一種算法更好，但我們可以說運行時間是O（min {L，| x |＆middot; 2 ^{| x |}）if你採取了兩種方法中更好的方法。

來源

2016-01-20 22:44:11 templatetypedef

謝謝你解釋。只有一件事，當你說「你可以從x中刪除字母形成w當且僅當x是w的子序列」時，你的意思是iff w是x右邊的子序列？ – Weltschmerz

@Weltschmerz是的...讓我解決這個問題。 :-) – templatetypedef

與我在答案上的觀點相似，如果您可以從單詞中間刪除字符，這將無法正常工作，對吧？ – JimmyJames

您可以構建一個trie，然後查看給定單詞適合的位置。您單詞的深度與最近的父母的差異在於所需的刪除次數。

來源

2016-01-20 22:46:15 JimmyJames

你確定這可以嗎？如果optima的選擇是刪除單詞中的第一個字母，那麼你最終會搜索錯誤的子樹。 – templatetypedef

好點。我認爲刪除是從結尾，但它並沒有說這個問題。 – JimmyJames

給定單詞成爲字典單詞的最小刪除次數

回答

相關問題