5

我有一个需要排序/过滤的项目列表（即字符串）。

最终结果不应包含任何重复（简单），我会将它们全部放入 Set 中。所以我现在有一组字符串。

更多解释..

我还有一个方法 x 可以计算两个字符串之间的差异量（使用列文斯坦距离）。

问题：

在将新字符串string插入我的 Set之前，我想使用方法set来检查levenstein 距离，以及 if返回的任何其他字符串x之间的距离，而不是我不应该添加它。stringsetx>=3

我最好的方法是什么？除了set每个string要插入的迭代槽？

4

3 回答 3

2

迭代Set将是您最好的选择，因为没有任何内置Set实现可以帮助您缩小可能性。

于 2012-05-23T16:24:57.477 回答
2

我已经玩弄了我的想法。如果没有任何迭代，我想不出一种方法来做到这一点。

假设您有一个名为distance(String,String):int返回两个字符串之间给定距离的方法。

String x = "Obi-wan"; //this is the item subject to eval addition
List<String> items = new ArrayList<String>(asList("Luke","Yoda","Anakin"));
if (items.filter(s -> distance(s, x) >= 3).getFirst() == null) {
  items.add(x);
}

如果您使用JDK8 Preview，您可以使用上面的代码立即执行此操作。Iterables.getFirst() 方法不会迭代整个集合，而只会迭代满足条件的第一个元素。

否则，您可能必须实现 Predicate 接口和过滤方法。

interface Predicate<T> {
    public boolean eval(T o);
}

public static void main(String[] args) {
   final String x = "Obi-wan"; //this is the item subject to eval addition
   List<String> items = new ArrayList<String>(asList("Luke","Yoda","Anakin"));
   Predicate<String> p = new Predicate<String>() {
       public boolean eval(String s){ 
           return distance(s, x) >= 3;
       }
   };
   if(filter(items, p).isEmpty()){ 
        items.add(x);
   }
}

public static <T> List<T> filter(List<? extends T> items, Predicate<? super T> predicate){
    List<T> destiny = new ArrayList<T>();
    for(T item : items){
       if(predicate.eval(item){
           destiny.add(item);
       }
    }
    return destiny;
}

或者，您可以在找到满足您条件的第一个项目后停止过滤。

于 2012-05-23T16:48:59.557 回答
1

您可以在创建集合时使用自定义比较器。在您的比较器中，如果它们相同（根据常规字符串比较规则）或者如果它们的 Levenstein 距离满足您的标准，则返回两个字符串相同。

当您的 comaprator 说两个字符串相同时，新字符串不会插入到集合中。（请注意，这意味着字符串的最终结果可能取决于插入的顺序）

更新：解决关于总订购的评论：

使用像上面建议的比较器会使最终结果取决于插入顺序（如上所述），就像任何其他解决方案一样，因为使用的 Levenstein 距离标准没有定义总排序。

OTOH，一旦一个字符串通过了不相等测试并被插入到集合中，集合中的其他字符串将不会与这个相等，因此集合中的字符串将使用它们的自然字符串排序，这确实定义了总排序，因此在集合的内部操作（例如排序）中不会出现进一步的不一致。

于 2012-05-23T16:32:12.443 回答