java – 在字典中查找所有有效单词的算法问题

发布时间：2020-12-15 08:31:12 所属栏目：Java 来源：网络整理

导读：给定一个字典(只是一个字符串列表). 您收到来自外部来源的未知数量的信件的Feed.给定一串字母,您将如何列出您可以从这些字母的任何组合中制作的所有有效单词(来自diciontary). 所以如果你收到：abpplead 你应该找到苹果,坏,垫,铅等. 我知道没有最好的答案.但

给定一个字典(只是一个字符串列表).

您收到来自外部来源的未知数量的信件的Feed.给定一串字母,您将如何列出您可以从这些字母的任何组合中制作的所有有效单词(来自diciontary).

所以如果你收到：abpplead

你应该找到苹果,坏,垫,铅等.

我知道没有最好的答案.但是有哪些合理有效的方法,使用什么数据结构等等.

此外,假设您可以预处理输入,因此您可以选择将输入字母存储在您想要的任何数据结构中.

将字典放入特里.然后将字母放入由其字符值索引的计数器数组中,保持每个字母的计数(让这称为[].).然后以深度第一搜索顺序遍历trie,在向下遍历时递减每个字母的计数[letter]值,并在返回的路上递增它.现在,任何时候计数[字母]即将消极,停止并向后移动.每次到达单词终止符时,输出结果.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!