给定单词成为字典单词的最小删除次数

给定一个字典作为散列表。找到给定单词所需的最少＃删除，以使它与字典中的任何单词匹配。给定单词成为字典单词的最小删除次数

有没有一些聪明的技巧来解决这个问题的小于指数复杂度（尝试所有可能的组合）？

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

给定单词成为字典单词的最小删除次数

回答

相关问题