2

我想比较提供的字符串是否以数组中的任何字符串开头。最简单的解决方案是：

String b = ...;
boolean matched = false;
for (String a : array) {
  if (b.startsWith(a))
    match = true;
}

但是，直观地说，我想使用类似 trie 的东西来提高效率，因为字符串数组可能会变得非常大，我需要快速运行这些匹配。我可以保证这些字符串都是按字母顺序排列的。我还可以保证数组中的所有字符串的长度都为 2 或更少。在 Java 中实现这种类似 trie 的结构的最佳方法是什么？我找不到任何基于 Java 的库可以做到这一点。

谢谢！

4

3 回答 3

5

如果您确实有足够的起始字符串使其成为瓶颈，那么尝试可能确实会有所帮助。

这个问题已经在这个网站上被问到并得到了回答：我在哪里可以找到 Java 中基于 Trie 的标准地图实现？

这就是答案： https ://forums.oracle.com/forums/thread.jspa?messageID=8787521

于 2013-04-16T18:47:12.777 回答
2

我想比较提供的字符串是否以数组中的任何字符串开头。

好吧-您当然可以改进当前的解决方案：

static boolean startsAny(final String b) {
    for (String a : array) {
        if (b.startsWith(a)) {
            return true;
        }
    }
    return false
}

您可以将String#matches与正则表达式一起使用，但我不确定这是否更有效。您是否分析了代码并将其确定为瓶颈？

于 2013-04-16T17:46:18.113 回答
2

一个简单的解决方案是将字符串插入到 a 中Set<String>，然后对其执行两次查找，一次查找第一个字符，b如果不匹配，则查找前两个字符b。

例如，

class StartsWithAny {
    private Set<String> set;

    public StartsWithAny(String[] array) {
        set = new HashSet<String>();
        for (String a : array) {
            set.add(a);
        }
    }

    // returns true if b starts with any strings contained in array
    // with the condition that b.length() <= 2
    public boolean startsWithAny(final String b) {
        if (b.length() > 0 && set.contains(b.substring(0, 1))) {
            return true;
        }

        if (b.length() > 1 && set.contains(b.substring(0, 2))) {
            return true;
        }

        return false;
    }
}

对此的一种变体是使用两个单独Set的 s，一个用于单字符查找，一个用于两个字符查找，这将稍微提高性能。

另一种类似的方法是实现一种二分搜索算法，该算法将对排序后的数组进行操作并执行类似的功能。

于 2013-04-16T18:29:05.710 回答