How to check String contains one of Strings in collection

Question

I want to check if the target string contains string in collections. And match the longest one. E.g.

Target string: str = "eignelaiwgn"

Collection strings: eig, a, eb, eigne, eignep

The result needs to be eigne

First I thought HashMap, but it is not sorted. So I try to put collection strings into ArrayList, then sort the list with string length. Then use for each loop to check

if ( str.contains("eigne") )

This needs to loop list each time. Is there a better(faster) way to achieve this?

You can use binary search technique after sorting the Arraylist to find the solution in log(n) time — pkgajulapalli, Dec 19 '18 at 06:30
Possible duplicate of [Java, return if List contains String](https://stackoverflow.com/questions/16218863/java-return-if-list-contains-string) — Lemmy, Dec 19 '18 at 06:31
@Lemmy , probable not. I want to check if target string contians string that in Collections. Not if the collection contains the target string. — Bejond, Dec 19 '18 at 06:34

fps · Answer 1 · 2018-12-19T14:48:09.663

Seems pretty straightforward with streams:

String targetString = "eignelaiwgn";
Collection<String> collection = Arrays.asList("eig", "a", "eb", "eigne", "eignep");

Optional<String> longestMatch = collection.stream()
    .filter(targetString::contains)
    .max(Comparator.comparingInt(String::length));

longestMatch.ifPresent(System.out::println); // eigne

This reads as: For every string in the collection, check if the target string contains it. If true, return the string with the max length. (As the collection might be empty, or as no string in the collection might match the filter, max returns an Optional<String>).

Nicholas K · Answer 2 · 2018-12-19T08:10:18.230

1

You could use a TreeSet for the same.

String str = "eignelaiwgn";
// Assuming that the 'sub-strings' are stored in a list
List<String> myList = Arrays.asList("eig", "a", "eb", "eigne", "eignep");

// Create a TreeSet that sorts based on descending order of length
Set<String> treeSet = new TreeSet<>((a, b) -> b.length() - a.length());
treeSet.addAll(myList);

String containsSub = treeSet.stream().filter(e -> str.contains(e))
                            .findFirst()
                            .orElse("Not found");

Now we iterate over the TreeSet and find the first occurrence where the sub-string is present in the original string. Now since the TreeSet is sorted in descending order of length, iteration will start from the highest to the lowest.

edited Dec 19 '18 at 08:10

answered Dec 19 '18 at 07:02

Nicholas K

15,148
7
31
57

Why are you using `TreeMap` instead of `TreeSet`? – chrylis -cautiouslyoptimistic- Dec 19 '18 at 07:32
Ironically, I was just thinking of changing that while having lunch! Guess you beat me to it. – Nicholas K Dec 19 '18 at 08:10

Jay Dangar · Answer 3 · 2018-12-19T06:38:01.130

0

you can use LevensteinDistance() method of StringUtils class in java which will tell you the number of changes needed to change one String into another.you can print string with minimum changes needed, which is your answer. see this document -> LevenshteinDistance

Also look for differences method for same class which will tell the difference between the two string.

edited Dec 19 '18 at 06:38

answered Dec 19 '18 at 06:32

Jay Dangar

3,271
1
16
35

score 0 · Answer 4 · answered Dec 19 '18 at 14:06

0

You could use a suffix tree. Please follow this link: https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

answered Dec 19 '18 at 14:06

vegeta

297
1
14

More explanation: https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english?rq=1 – vegeta Dec 19 '18 at 14:19

How to check String contains one of Strings in collection

4 Answers4