user7486618
user7486618

Reputation:

Checking list of strings entirely contained in other list of strings

I wrote this piece of code to check wheter a list of strings is entirely contained in another one and in that case delete the list.

public static void main(String[] args) {
    LinkedList<String> l1 = new LinkedList<String>();
    LinkedList<String> l2 = new LinkedList<String>();
    l1.add("Cc");
    l1.add("Dd");
    l2.add("Cc");
    l2.add("Dd");
    l2.add("Ee");
    LinkedList<LinkedList<String>> l = new LinkedList<LinkedList<String>>();
    l.add(l1);
    l.add(l2);
    System.out.println("OUTPUT: " + filterSublist(l));

}

static List<LinkedList<String>> filterSublist(LinkedList<LinkedList<String>> l) {
    List<LinkedList<String>> uniq = new LinkedList<LinkedList<String>>(l);
    l.forEach(elem -> uniq.removeIf(x -> !x.equals(elem) && elem.contains(x)));
    return uniq;
}

The function filterSubList should return a list of list of strings which has no lists that are totally contained in other lists. In the example we have:

Since list 1 is entirely contained in list 2, the function should return a list of lists that contains only list 2. But when I run the program I got output which is a list that contains both:

OUTPUT: [[Cc, Dd], [Cc, Dd, Ee]]

This is wrong. Is there a mistake in the filterSubList function?

Upvotes: 0

Views: 74

Answers (2)

dev8080
dev8080

Reputation: 4020

You are checking for one list (object) containing another list (object). A new list will be alloted differently in memory whenever a new object is created, Instead check for the objects inside with containsAll:

Try this instead:

static List<LinkedList<String>> filterSublist(LinkedList<LinkedList<String>> l) {
List<LinkedList<String>> uniq = new LinkedList<LinkedList<String>>(l);
l.forEach(elem -> uniq.removeIf(x -> !x.equals(elem) && elem.containsAll(x)));
return uniq;
}

In case Rene's raised some points relevant to the OP, here's an implementation that pretty much follows his lead, in a different way, though.

static List<LinkedList<String>> filterSublistAlternate(LinkedList<LinkedList<String>> l) {
boolean[] removed = new boolean[ l.size() ]; 
outer: for(int i=0; i< l.size() ; i++)
    inner: for(int j=0; j< l.size() ; j++)
    {
        if( i != j )
        if(l.get(j).containsAll(l.get(i)))
        {
            System.out.println(i+" and "+j);
            if(l.get(i).size() == l.get(j).size())
                if(removed[i] == removed[j] && !removed[i])
                    removed[i] = true;
                else
                    continue outer;
            else
            {
                removed[i] = true;
                continue outer;
            }

        }
    }

for(int i=removed.length-1; i>=0  ; i--)
    if(removed[i])
        l.remove(i);

return l;
}

Upvotes: 1

Ren&#233; Scheibe
Ren&#233; Scheibe

Reputation: 2080

I propose the solution below as it is:

  • more memory efficient as it doesn't duplicate the original list
  • more correct as it really checks for sublists (not just single element existence)
  • more correct as it removes duplicates from the result

Code:

static List<LinkedList<String>> filterSublist(LinkedList<LinkedList<String>> l) {
    return l.stream()
        .filter(x -> l.stream().noneMatch(elem -> !elem.equals(x) && Collections.indexOfSubList(elem, x) != -1))
        .distinct()
        .collect(Collectors.toList());
}

Upvotes: 0

Related Questions