我试图解决problem，基本上我们需要从字典中找到所有具有字典顺序的给定前缀的单词 .
我正在使用Trie数据结构来完成任务，但我的解决方案只是超时判断，什么可以是更有效/更快的方法来解决这个问题？
我目前的实施是
class trie{
node root=new node();
class node{
node child[]=new node[26];
boolean is_leaf=false;
}
public void add(char c[])
{
node root=this.root;
int pos=0,c1=0;
while(pos<c.length)
{
c1=c[pos]-'a';
if(root.child[c1]==null)
{
root.child[c1]=new node();
}
root=root.child[c1];
pos++;
}
root.is_leaf=true;
}
public ArrayList<String> search(String s)
{
char c[]=s.toCharArray();
node root=this.root;
int pos=0,c1=0;
while(pos<c.length)
{
c1=c[pos]-'a';
if(root.child[c1]==null)
{
root.child[c1]=new node();
}
root=root.child[c1];
pos++;
}
ArrayList<String> ans=new ArrayList<>();
build_recursive(root,s,new StringBuilder(),ans);
return ans;
}
public void build_recursive(node root,String prefix,StringBuilder cur, ArrayList<String> ans)
{
if(root.is_leaf&&cur.length()!=0)
{
String s=prefix+cur.toString();
ans.add(s);
}
for(int i=0;i<26;i++)
{
if(root.child[i]!=null)
{
char c=(char) (i+'a');
cur.append(c);
build_recursive(root.child[i], prefix, cur, ans);
cur.deleteCharAt(cur.length()-1);
}
}
}
}
函数Search返回共享给定前缀的所有单词的排序列表 .
还有一个更好的数据结构我可以用于此吗？
1 回答
尝试很好地找到另一个字符串的子串 . 但是，您正在搜索字典中的单词 - 子字符串匹配不是必需的 . 此外，一旦找到带有前缀的第一个单词，下一个单词（如果存在）将紧挨着它 . 无需复杂搜索！
尝试也会从节点构建中带来很多开销，然后需要使用指针（=额外空间要求）来引用 . 指针很慢 . 在C中，迭代链接列表can be 20x slower而不是迭代数组，除非节点都是很好的排序 .
很可能，这个问题可以通过解决
将所有单词读入String的StringList：O（n），其中n =单词
排序ArrayList：O（n log n）
并为每个前缀查询，
使用binary search查找前缀的第一个匹配项：O（log n），它已经在标准库中实现
返回匹配的连续元素，直到匹配耗尽：O（m），m =匹配数
这比尝试理论上的复杂性更快，并且由于内存布局而快得多 - 当你不需要这样做时，搞乱指针是很昂贵的 .