remove elements in array which are substring of other elements in Java

Question

I have a Arraylist of strings. I want to remove the strings that are substring of another string in that array. I have a python implementation but with java is tricky. Python

def filterSublist(lst):
 uniq = lst
 for elem in lst:
    uniq = [x for x in uniq if (x == elem) or (x not in elem)]
 return uniq

For java, I need to check if the element is contained in another element, if yes, then nothing, if not adding it to another one.

for(String element : list){
    for(int j = 0; j < list.size(); j++)
        if (! element.contains(list.get(j))){
            listUniq.add(date);}
}

The java solution doesn't work as it should. one reason is that it also compares element to the element itself. Any help is appreciated.

1) Use curled braces for every statement where possible - you might omit it, but it really is bad style. 2) You already compare every element of the list with every other element, but you omit the x == elem part of python. — Smutje
– Smutje, Commented Mar 13, 2015 at 22:48

fps · Accepted Answer · 2015-03-14 02:54:14Z

4

With Java 8, you could use lambdas and the streaming API in a straightforward manner:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Sample {

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

    public static void main(String[] args) {
        Sample sample = new Sample();

        List<String> filtered = sample.filterSublist(
            Arrays.asList("hello", "there", "the", 
                          "low", "hell", "lower", "here"));

        System.out.println(filtered); // [hello, there, lower]
    }
}

I've just negated the predicate in the removeIf() method, since I'm removing elements instead of adding them.

edited Mar 14, 2015 at 2:54

answered Mar 14, 2015 at 2:39

fps

34.5k8 gold badges62 silver badges116 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vladislav Lezhnin · Accepted Answer · 2015-03-13 23:08:30Z

Here is my suggested solution.

public Set<String> getUnique(List<String> source) {
            HashSet<String> result = new HashSet<String>();

            boolean contains = false;
            for (String s : source) {
                for (String unique : result) {
                    if (unique.contains(s)) {
                        contains = true;
                        break;
                    } else if (s.contains(unique)) {
                        result.remove(unique);
                        result.add(s);
                        contains = true;
                        break;
                    }
                }
                if (!contains) {
                    result.add(s);
                }
            }

            return result;

        }

In this solution we don't iterate over the whole collection each time but only checking if element is contained in result set. If there are many matches, we can save a lot of iterations.

condorcraft110 II · Accepted Answer · 2015-03-14 22:34:14Z

2

You could try brute-force comparing every string to every other (except itself):

List<String> toRemove = new ArrayList<>();
for(int i = 0; i < list.size(); i++)
{
    String element0 = list.get(i);
    for(int j = 0; j < list.size(); j++)
    {
        String element1 = list.get(j);
        if(!element0.equals(element1) && element0.contains(element1) && !toRemove.contains(element1)) toRemove.add(element1);
    }
}

list.removeAll(toRemove);

edited Mar 14, 2015 at 22:34

answered Mar 13, 2015 at 22:47

condorcraft110 II

2611 gold badge2 silver badges15 bronze badges

5 Comments

RealSkeptic Over a year ago

element0 != element1 is not how you compare strings in Java.

condorcraft110 II Over a year ago

@RealSkeptic I know, I'm deliberately comparing the references.

condorcraft110 II Over a year ago

@RealSkeptic I'm trying to answer the OP's question, not directly port their Python code. I suppose, though, it would instil good practice in the OP if they're new to Java because equals() does compare references.

RealSkeptic Over a year ago

My point is that you are not returning the same result. I just tried both yours and the python's. Yours removes duplicates, the Python's doesn't. The OP's definition, based on that implementation, is that "foo" is not a substring of "foo". Also, yours simply doesn't work. Try it with "abc","def","abcde", "def", "i","mim". Should remove the "abc" and the "i".

condorcraft110 II Over a year ago

@RealSkeptic Addressed your issues and made it actually work - I'd made some stupid typos >_<

Collectives™ on Stack Overflow

remove elements in array which are substring of other elements in Java

3 Answers 3

Comments

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related