完全公开，这是针对算法类(class)中的作业，但我并不是在找人为我编写任何代码或牵着我的手。无论如何，我们必须做 Boggle 游戏。对于那些不知道的人，基本上你会得到一个 Boggle 板，并且必须找到尽可能多的单词，考虑到递归的字符串可能性，这可能会花费大量时间。
为了缩短 OP 时间，我们被鼓励使用任何我们想尝试的算法，并在进行过程中“清除”字符串。目前我有一个系统可以通过将它们存储在字典中找到所有可能的 3 个字母后缀，如果字符串有 3 个字母但不匹配任何有效的后缀，递归将停止。
进入问题的关键，我正在尝试实现一个 Radix 后缀树，目前它看起来像这样
public static class BoggleRadix
{
private Node root;
public BoggleRadix()
{
}
public class Node
{
public Node()
{
List<Edge> nodeEdges = new List<Edge>()
{
}
}
}
public class Edge
{
public String edgeString;
public Node edgeNode;
public Edge()
{
}
public Edge(String s, Edge e)
{
this.edgeString = s;
this.edgeNode = e;
}
}
}
所以我将指针存储在一个无序列表中，这意味着如果我要检查后缀，我可以预期，更糟的情况下，甚至需要 26 次操作才能找到我需要继续沿着树向下的后缀指针。
有什么方法可以加快插入速度，简化流程吗？是否值得为每个节点在内存中构建一个小字典来检查后缀的第一个字母是否存在？这是微不足道的吗？
最佳答案
我同意 jimktrains 的建议，即使用数组而不是后缀的链表。您可以转换大写 ASCII 字母 c使用 (int)c - (int)'A' 的数组索引.对我的系统字典的测试表明只有几千个三字母前缀，所以空间使用应该不是问题。
另一方面，您可以将整个字典存储为 deterministic acyclic finite state automaton .那么尝试节省空间可能是明智的。我建议使用位图，而不是无法预测分支的二进制搜索。在每个节点中，都有一个字段 int bitmap;等于 | 的按位或(0 运算符，带有标识元素 (1 << i) )对于每个占用索引 i在未压缩的数组中。然后，测试未压缩索引的存在 i , 检查是否 bitmap & (1 << i)是非零的。如果是这样，那么压缩数组的索引是 Integer.bitCount(bitmap & ((1 << i) - 1)) .
关于java - 为构建基数搜索树匹配字符串前缀的最快方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25743753/