An efficient way to find all strings of an Arraylist that contains a substring
I have a string, say a="1.1"
and an arraylist, let's say list
that has strings:"1.1.1.1", "1.1.2.4","1.2,1.3","1.5.1.1"
Now I want to get lines from this arraylist which contains the string a = "1.1" at the beginning, which means that a is a substring of that string and must match the beginning.
So, for this case, the answer will be 1.1.1.1
and 1.1.2.4
, but not 1.5.1.1
, since here 1.1 is not at the beginning.
I know how to achieve this, but I think my solution is not efficient enough and for a large arraylist, it will take more processing time.
My approach: Run a for loop on the arraylist and for each line, trim the string from the beginning with lenth of a and check if the trimmed string is equal with.
But if I want to repeat this for multiple lines for a large arraylist, I think this is not a good solution.
Any idea? I appreciate your help.
source to share
Hey how do you want some optimized solution so you can try:
- sort the list with
Collections.sort(list);
- find a match for the first string using a binary search and make a flag that contains that prefix.
- now if the next line does not match this prefix, which means the next line of the list will not match this prefix as we sorted the collection
Try this code:
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class T {
static int count=0;
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
// for testing purpose only i am making this list and putting this data
for (int i = 101; i < 501; i++) {
list.add(i + "");
}
boolean matchedSuffix = false;
String prefix = "30";
Collections.sort(list);
int startFrom = T.binarySerchOverList(list, prefix);
if (startFrom == -1) {
System.out.println("no data found");
} else {
for (int i = startFrom;; i++) {
String s = list.get(i);
if (s.startsWith(prefix)) {
//here you will get matching strings
System.out.println(s);
matchedSuffix = true;
} else {
if (matchedSuffix) {
break;
}
}
}
}
}
public static int binarySerchOverList(List<String> input, String prefix) {
count++;
System.out.println( "iteration count is "+count);
int size = input.size();
int midpoint = size / 2;
int startPoint = 0;
String stringToTest = input.get(midpoint);
if (stringToTest.startsWith(prefix)) {
startPoint = midpoint - 1;
while (true) {
if (!input.get(startPoint).startsWith(prefix)) {
startPoint++;
break;
}
if (startPoint == 0) {
break;
}
startPoint--;
}
return startPoint;
}
if (stringToTest.compareTo(prefix) > 0) {
List<String> sublist = input.subList(0, midpoint);
return binarySerchOverList(sublist, prefix);
}
if (stringToTest.compareTo(prefix) < 0) {
if (input.get(input.size() - 1).compareTo(prefix) < 0) {
return -1;
}
List<String> sublist = input.subList(midpoint, input.size());
return binarySerchOverList(sublist, prefix);
}
return 0;
}
}
Ask me if you have any doubts about the code
source to share
This method will work:
public static List<String> findWithPrefix(List<String> list, String prefix) {
List<String> result = new ArrayList<>();
for(String s : list)
if(s.startsWith(prefix))
result.add(s);
return result;
}
If you can use Java 8, this will be shorter:
public static List<String> findWithPrefixJava8(List<String> list, String prefix) {
return list.stream()
.filter(str -> str.startsWith(prefix))
.collect(Collectors.toList());
}
source to share
If you want to loop through the list and pull out all the lines starting with 1.1
, then the use startsWith(String subString)
should do what you need. You can use Java 8Collection.parallelStream().forEach...
If, on the other hand, you want to do multiple searches, every time any string starts with a different substring (starting from what it is here), you can take a look at suffix trees .
The suffix tree will index all of your rows as a tree. This way, you can search for a tree starting at the root node, and then after you find a node that satisfies your condition, you just keep going through it to get the rows.
root
/ | \
1 2 3
/ |
. 0
/ |
1 2
| |
[1.1] [1.2]
The values in square brackets indicate where the found substring is located, which in your case will consist of the entire string.
source to share
Here's an idea, but I don't know if that's enough. How about combining all the elements in such a way that you can find out which element was with: for example:
{0: 1.1.2.4}, {1: 1.2.1.3}, .....
then run a string regex query that returns all substrings that start with {and end with a} and start with 1.1. You can define a named group that will contain the index number so that you have all the indexes in one pass.
source to share