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

How to check if a list contains a sublist in a given order in Java

提问by anamar

I read in groovy how to check if a list contains a sublist - stackoverflow.

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

I am interested if there is a way of checking whether list contains sublist, but in a given order. For example, this code will give true,

如果有一种方法可以检查列表是否包含子列表，但按照给定的顺序，我很感兴趣。例如，此代码将给出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));

But I want to get falseback.

但我想得到假回来。

回答by Jordi Castilla

You can use method Collections.indexOfSubList.

您可以使用方法Collections.indexOfSubList。

Returns the starting position of the first occurrence of the specified target list within the specified source list, or -1if there is no such occurrence. More formally, returns the lowest index i such that source.subList(i, i+target.size()).equals(target), or -1if there is no such index. (Returns -1if target.size()> source.size().)

返回指定源列表中指定目标列表第一次出现的起始位置，或者-1如果没有这样的出现。更正式地，返回最低索引 i source.subList(i, i+target.size()).equals(target)，-1如果，或者如果没有这样的索引。（-1如果target.size()> 则返回source.size()。）

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

SHORT:
If Collections.indexOfSubList(list , sublist) =! -1you will have a match

简短内容：
如果Collections.indexOfSubList(list , sublist) =! -1你有一场比赛

回答by Lluis Martinez

Cheap but ugly solution:

便宜但丑陋的解决方案：

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

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

回答by tobias_k

Not entirely clear from your question: If the sublist can be contained in the list in order, but with other elements in between, you can use something like this:

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

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;
}

With list = ["PRP", "VBP", "VBN", "NN", "NNS", "MD", "VB"], this returns falsefor sublist = ["MD", "VB", "VBN"], and truefor sublist = ["PRP", "VBN", "VB"].

有了list = ["PRP", "VBP", "VBN", "NN", "NNS", "MD", "VB"]，这个回报false的sublist = ["MD", "VB", "VBN"]，并true为sublist = ["PRP", "VBN", "VB"]。

回答by Margus

I found it necessary to comment that @JordiCastilla solution is not correct in the sense that it is complete. It can be correct if item type has correct equals, because in case of Collections.indexOfSubListyou invoke list element type equals.

我发现有必要评论@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);

This however is trivially culture dependent and in case of type String is incorrect. Consider for example the case:

然而，这与文化无关，并且在 String 类型不正确的情况下。例如考虑这样的情况：

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

I think reasoning behind it is that character count does not match - in any case it is not correct. You would think that "at least they got the basics down right" - and you would be wrong :

我认为其背后的原因是字符数不匹配 - 在任何情况下都是不正确的。您会认为“至少他们掌握了正确的基础知识”-您会错的：

"You should be aware that internationalization and localization issues of full Unicode strings are not addressed with [String] methods. For example, when you're comparing two strings to determine which is 'greater', characters in strings are compared numerically by their Unicode values, not by their localized notion of order."

“您应该意识到，[String] 方法无法解决完整 Unicode 字符串的国际化和本地化问题。例如，当您比较两个字符串以确定哪个“更大”时，字符串中的字符将通过它们的 Unicode 进行数字比较价值观，而不是他们本地化的秩序概念。”

In Unicode however same string can have multiplerepresentations and they would not equate. Type String is an example but you could have any custom data type.

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

Long story short: make sure your item type equals has the correct implementation.

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

---

---

Another example how this can trivially be wrong is following:

另一个例子如下：

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

First list contains second one and they have the same order, but in between elements target elements source contains other elements.

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

To find that you can use something in the lines :

要发现您可以在行中使用某些内容：

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;    
}

(NB : code examples not tested and written from head)

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