java - java中创建单词的高效算法

Question

我正在使用 libGDX 框架开发一个文字游戏，我想实现一个基本的提示功能，系统可以根据该功能从棋盘上提供的 17 个字母中生成一个有效的 7 个字母的单词。现在，船上 17 个字母(可供选择)的设置是完全随机的，所以我不能使用预先确定的提示词来提示(比如 4 图片 1 个单词)。

我的解决方案是通过从提供的 17 个字母中找到所有可能的 7 个字母组合来进行一些组合。接下来，我排列了每个组合并使用 wordSet English Lexicon 对它们进行了交叉检查，我获得的第一个有效单词将是提示词。

正如您已经猜到的那样，此过程的任务是知道 17 排列 7 已经等于 9800 万种可能的排列。为了弥补这一点，我使用了一个FixedThreadPool来拆分排列任务(分成大约20个工作线程)，我现在有一个相对快速的单词搜索，但缺点是，这会导致严重的延迟低端设备。

任何关于如何制作更好的提示词搜索算法或改进我上面解释的方法的建议都将不胜感激。

Answer 1

使用您的单词列表构建一个 trie/前缀树:

您可以从 17 个可用字母中随机选择一个字母，并开始仅使用 17 个字母中的字母进行遍历。第一个带有标志的节点表明这标志着一个单词的结尾可以是一个建议。

很多预测文本程序都使用这样的结构来猜测您正在输入的单词，或者如果您在图表中距离标记单词结尾的节点不太远，则可以帮助您纠正打字错误。它在空间上更好，因为树的深度由最长的单词决定。但是，您不会在以下情况下浪费空间:

do
dog
doggy
done
dunce

您只存储:

                d
               / \
             *o   u
             / \   \
           *g   n   n
           /     \   \
          g      *e   c
         /             \
       *y              *e

其中 * 是一个 boolean 标志，指示单词结束的位置。

时间复杂度:

判断一个文本字符串是否是一个单词将是 O(n)，其中 n 是单词的长度。

这个站点似乎有一些优化:https://www.geeksforgeeks.org/trie-insert-and-search/

空间，取决于您是使用数组、指针还是 HashMap 来实现。