java - 通过一次将一个字符添加到输入字符串中可以形成的最长字符串

Question

所以我最近在一次采访中得到了这个问题：

给定一个字典和一个起始字符串，通过在输入字符串的前后添加一个字符可以形成的最长单词是多少，并且每个新单词也必须出现在字典中？

例如：input = 'at' Dict = {hat, chat, chats, rat, tat, tats, chatats}

返回“聊天”，因为：在 -> 帽子 -> 聊天 -> 聊天

我想到了一个解决方案，我们暴力破解并尝试将 a - z 的所有字母添加到输入字符串的前后，如果存在新字符串，那么我们再次暴力破解这 26 个字母，最终得到最终的字符串。

我想知道是否有更有效的方法来解决这个问题，而无需每次都强制所有 26 个字母前后移动？

我想到的一种方法是遍历字典，如果输入字符串作为长度大于更改输入字符串长度 1 的任何条目的子字符串存在，则从条目字符串中删除输入子字符串。

例如：在第 1 次迭代之后，dict 将是 = {h, chat, chats, r, t, tats, chatats}

我们还将为每个条目设置一个长度变量来跟踪条目的原始长度。但我不确定这是否是正确的方法/甚至会起作用。

Answer 1

构建一个单词图及其较短/较长的版本，例如对于问题 ( hat, chat, chats, rat, tat, tats, chatats) 中的单词列表，这将是：

                           chatats
hat ─── chat ─── chats
rat
tat ─── tats

向后构建图形，即对于每个单词，通过删除前导字符或尾随字符来查找 2 个较短的单词。

Map为了更快地查找，为他们的图形节点构建一个单词。

现在找到图中最长的链。