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

Question

I read in groovy how to check if a list contains a sublist - 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,

    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 false back.

Solution 1

You can use method Collections.indexOfSubList .

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

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

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

Solution 2

Cheap but ugly solution:

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

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

Solution 3

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 false for sublist = ["MD", "VB", "VBN"], and true for sublist = ["PRP", "VBN", "VB"].

Comments

[anamar]

Thank you, this is what I needed.

[Jordi Castilla]

check my sollution, Collections is your friend / mira't la meva sol.lució, Collections es el teu amic ;)

[Lluis Martinez]

I agree 100%, I use Apache Commons every day :-)

[anamar]

I don't allow other elements in-between. @JordiCastilla provided solution I was looking for.

[tobias_k]

Why should ss be considered equal to ß? ß is not just a typographic ligature, but a different letter. "in Massen" has a totally different pronunciation and meaning than "in Maßen". Also, why do you think this would be relevant in OP's case? About your "another example": This is how I understood the question, too, but apparently its wrong...

[Margus]

In second case I wanted to point out { A, B, C } contains ordered list { A, C }, but elements are not consequent. In first case I wanted to point out equality has cultural component and most are oblivious about it. You can think of a better example out of a whim, I on the other did not. In addition for contrast in C#.Net "Strasse".Equals("Straße", StringComparison.InvariantCulture);" would return true (same for CompareTo).

[Christopher Helck]

This is incorrect if last element in sublist is not in list. It can return true. Simplest example is when sublist contains one value which is not in list. Function returns true. Should be false.