如何在Java中检查列表是否包含给定顺序的子列表

Question

我在 groovy 中阅读了 如何检查列表是否包含子列表 - stackoverflow 。

我感兴趣是否有一种方法可以检查列表是否包含子列表，但按给定的顺序。例如，此代码将给出 true,

    List<String> list = Arrays.asList("PRP", "VBP", "VBN", "NN", "NNS", "MD", "VB");
    List<String> sublist = Arrays.asList("MD", "VB", "VBN");
    System.out.println(list.containsAll(sublist));

但我想找回false。

Answer 1

可以使用方法

Collections.indexOfSubList

.

返回指定源列表中指定目标列表第一次出现的起始位置，如果没有出现则返回

-1

。 更正式地说，返回满足

source.subList(i, i+target.size()).equals(target)

的最低索引 i，如果没有这样的索引，则返回

-1

。 （如果

-1

>

target.size()

，则返回

source.size()

。）

int index=Collections.indexOfSubList(list , sublist);

简短：

如果

Collections.indexOfSubList(list, sublist) != -1

你将会有一场比赛

Answer 2

廉价但丑陋的解决方案：

String listStr = list.toString().replace("[", "").replace("]", "");
String sublistStr = sublist.toString().replace("[", "").replace("]", "");

System.out.println(listStr.contains(sublistStr));

Answer 3

您的问题并不完全清楚：如果子列表可以按顺序包含在列表中，但中间有其他元素，您可以使用如下内容：

public static <T> boolean containsInOrder(List<T> list, List<T> sublist) {
    Iterator<T> listIter = list.iterator();
    for (T item : sublist) {
        if (! listIter.hasNext()) {
            // still elements in sublist, but none in list
            return false;
        }
        while (listIter.hasNext() && ! listIter.next().equals(item)) {
            // do nothing, just consume the list until item is found
        }
    }
    // entire sublist found in list
    return true;
}

使用

list = ["PRP", "VBP", "VBN", "NN", "NNS", "MD", "VB"]

，对于

false

返回

sublist = ["MD", "VB", "VBN"]

，对于

true

返回

sublist = ["PRP", "VBN", "VB"]

。

Answer 4

我发现有必要评论@JordiCastilla 解决方案从完整的意义上来说是不正确的。如果项目类型具有正确的 equals，则它可能是正确的，因为在 Collections.indexOfSubList 的情况下，您调用列表元素类型 equals。

/**
 * Compares the specified object with this list for equality.  Returns
 * <tt>true</tt> if and only if the specified object is also a list, both
 * lists have the same size, and all corresponding pairs of elements in
 * the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
 * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
 * e1.equals(e2))</tt>.)  In other words, two lists are defined to be
 * equal if they contain the same elements in the same order.  This
 * definition ensures that the equals method works properly across
 * different implementations of the <tt>List</tt> interface.
 *
 * @param o the object to be compared for equality with this list
 * @return <tt>true</tt> if the specified object is equal to this list
 */
boolean equals(Object o);

然而，这在很大程度上取决于文化，并且如果字符串类型不正确。例如考虑以下情况：

String a = "ss";
String b = "ß";                  //german "ss" character
Assert.IsTrue(a.equals(b));      //in java, this will return false even in DE locale

我认为其背后的原因是字符数不匹配 - 无论如何它都是不正确的。你可能会认为“至少他们掌握了正确的基础知识”——但你错了：

“你应该意识到国际化和本地化问题 的完整 Unicode 字符串未使用 [String] 方法进行寻址。为了 例如，当您比较两个字符串以确定哪个是 'greater'，字符串中的字符按其数字进行比较 Unicode 值，而不是本地化的顺序概念。”

然而，在 Unicode 中，同一个字符串可以有 多个 表示形式，并且它们不会相等。字符串类型是一个示例，但您可以使用任何自定义数据类型。

长话短说：确保您的项目类型 equals 具有正确的实现。

---

这可能是微不足道的错误的另一个例子如下：

List arrlistsrc = new ArrayList();
List arrlisttarget = new ArrayList();

arrlistsrc.add("A");
arrlistsrc.add("B");
arrlistsrc.add("C");

arrlisttarget.add("A");
arrlisttarget.add("C");

int index = Collections.indexOfSubList(arrlistsrc, arrlisttarget); // this will be -1

第一个列表包含第二个列表，它们具有相同的顺序，但在元素之间目标元素源包含其他元素。

发现你可以在行中使用一些东西：

boolean ContainsOrderedSublist<T>(IList<T> arrlistsrc, IList<T> arrlisttarget){
    int slider = 0;
    for (String val: arrlisttarget ) {
        slider = arrlistsrc.indexOf(val, slider);// or use culture independent version
        if(slider < 0) break;
    }
    return slider < 0;    
}

（注意：代码示例未经测试和从头编写）