当我看到一个问题询问我是否可以从字符串中找到最长的单词(字符串没有空格只有字符)时，我开始研究一些算法问题。想了想，我只是想确认是否可以用动态规划来解决这个类似于最大连续和问题的问题。在解析完每个字符后，我可以调用 isWord 方法(已经实现)然后如果它继续转到下一个字符并增加单词长度，如果不是则简单地将计数器重置为零并开始从该索引中寻找单词.请让我知道这是否是一个好方法，否则请指导我解决此问题的更好方法。
感谢您的帮助。
-维克
最佳答案
此算法将无法正常工作。考虑以下字符串:
BENDOCRINE
如果你从字符串的开头开始向前扫描，而你还有一个单词，你会找到单词“BEND”，然后在该点之后重置字符串并从 O 开始。这里的正确答案是而不是选择“内分泌”这个词，这个词要长得多。
如果您有一个静态词典，并且想从该词典中找到文本字符串中包含的最长单词，您可能需要查看 Aho-Corasick algorithm ，它将在文本字符串中找到一组字符串的每一个匹配项，并且效率极高。您可以轻松地修改算法，以便它随时跟踪它输出的最长单词，这样它就不会输出比目前发现的最长单词更短的字符串，在这种情况下，运行时间将为 O(n + m)，其中n 是要搜索的文本字符串的长度，m 是所有合法英语单词中的字符总数。此外，如果预先进行 O(m) 的预处理，从那时起，您可以在 O(n) 的时间内找到给定字符串中最长的单词，其中 n 是字符串中的字符数。
(至于为什么会在O(n + m)时间内运行:通常运行时间是O(n + m + z)，其中z是匹配数。如果你限制输出的匹配数，那么你永远不要输出比目前最长的单词更短的单词，最多可以输出 n 个单词。因此运行时间为 O(n + m + n) = O(n + m))。
希望这对您有所帮助!
关于string - 使用动态编程查找字符串中最长的单词？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11269266/