有效地从一组中获取字符串"startingWith"的子集

Question

我有一个大组字符串,我想为它创建一个自动提示功能.

假设该集合是 ["foo", "fighter"]

键入"f"应该返回两个值,键入"fo"应该只返回"foo".

目前我只是通过调用迭代设置和归档结果startsWith,但是它太慢了.

TreeSet具有子集功能的标准在这里没有多大帮助,因为它只实现了RB树.

Java API中是否存在有效的解决方案,还是必须构建自己的Set实现？

---

编辑:我的实现看起来像这样,使用Andrey Naumenkos trie数据结构.如果要使用扩展ASCII字符,请注意增加数组大小.如果您使用的是List代替,Map则按排序顺序获得结果.

public Set<String> getSubset(String s) {
    result = new HashSet<String>();
    getSubset(root, s);
    return result;
}

private void getSubset(TrieNode node, String s) {
    TrieNode n = node;
    for (char ch : s.toCharArray()) {
        if (n.children[ch] != null) {
            n = n.children[ch];
            continue;
        }
        return;
    }
    getSubsetR(n, s);
}

private void getSubsetR(TrieNode node, String s) {
    for (char ch = 0; ch < node.children.length; ch++) {
        TrieNode child = node.children[ch];
        if (child != null)
            getSubsetR(child, s + ch);
    }
    if (node.leaf) {
        result.add(s);
    }
}

Answer 1

您正在寻找的是前缀树数据结构:http://en.wikipedia.org/wiki/Trie

这里的代码可以帮助您入门:https://sites.google.com/site/indy256/algo/trie