从集合中有效地获取字符串子集 "startingWith"

Question

我有一组大字符串，我想为它创建一个自动建议功能。

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

输入 "f" 应该 return 两个值，输入 "fo" 应该只 return "foo".

目前我只是通过调用 startsWith 遍历集合并归档结果，但是它太慢了。

标准 TreeSet 及其子集函数在这里没有多大帮助，因为它只实现了 RB 树。

Java API 中是否有有效的解决方案，或者我必须构建自己的 Set 实现？

编辑：我的实现看起来像这样，使用 Andrey Naumenkos trie datastructures。如果要使用扩展的 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

从集合中有效地获取字符串子集 "startingWith"

Efficiently get subset of strings "startingWith" out of a set

java

algorithm

dictionary

substring

subset