执行字符串startsWith

我想，如果提供的字符串与任何一个数组的字符串开始比较Java的最佳途径。最简单的解决方案之中：执行字符串startsWith

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

然而，直觉，我想使用类似特里结构以获得更好的效率，因为字符串数组可能增长到相当大的，我需要运行这些比赛很快。我可以保证这些字符串都是按字母顺序排列的。我还可以保证数组中的所有字符串的长度都是2或更小。在Java中实现这种类似于trie的结构的最佳方式是什么？我找不到任何这样做的基于Java的库。

谢谢！

来源

2013-04-16 Jin

你可能看http://stackoverflow.com/questions/623892/where-do -i-发现 - 一个标准 - 特里基于地图的实现功能于Java或有关分析第一本https://forums.oracle.com/forums/thread.jspa?messageID=8787521 – CPerkins

一个简单的解决方案是将字符串插入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-16 18:29:05

我真的结束了简单地使用TreeSet并做一个contains（）查找，不知道这是否比单独查找显着更慢/更快，但它只有2个字符，所以它应该没有那么大的不同，我想..谢谢对于这个建议！ – Jin

我想比较，如果提供的字符串与任何一个数组中的字符串的开始。

嘛 - 你当然可以在当前解决方案提高：

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

可以使用String#matches用正则表达式，但我不知道这是更有效的。你是否分析了代码并将其识别为瓶颈？

来源

2013-04-16 17:46:18

这个问题问得好，这速度更快（但不会编译 - 它需要最后一个'return false'）。 – CPerkins

好的建议分析..这可能是我优化得太早，我会运行一些测试，看看。 – Jin

哎呀，谢谢。 –

如果你真的有成为一个瓶颈，一个线索可能确实帮助不够开头的字符串。

这个问题已经被问和回答了这个非常网站：Where do I find a standard Trie based map implementation in Java?

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

来源

2013-04-16 18:47:12 CPerkins

感谢您的链接，我记得看过帖子，没有看到标准的实施。我最终只使用了一个普通的TreeSet，并在获取其他库之前首先分析性能。再次感谢！ – Jin

加1为链接 –

执行字符串startsWith

回答

相关问题