0

I have a string, say a="1.1" and an arraylist, say list, which has the strings: "1.1.1.1", "1.1.2.4","1.2,1.3","1.5.1.1"

Now, I want to get the strings from this arraylist, which contains the string a="1.1" at the beginning, that means a is a substring of those string and need to match from beginning.

So, for this case, answer will be 1.1.1.1 and 1.1.2.4 but not 1.5.1.1 as 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 large arraylist, it will take more processing time.

My approach: Run a for loop for the arraylist and for each string, crop the string from the beginning with the lenth of a and check if cropped string is equal with a.

But if I want to repeat this for several strings for a large arraylist, I think it is not a good solution.

Any idea? I will highly appreciate your help.

Improve this question
4
  • 2
    You could use the startsWith(String str) method of the String class Commented May 6, 2015 at 10:40
  • You can use startsWith(String s) instead. Have a look Commented May 6, 2015 at 10:40
  • Please post your code. Commented May 6, 2015 at 10:43
  • If you need to do this more than once, it's almost definitely worth sorting the list instead. Then you can do binary search. Commented May 6, 2015 at 10:43

7 Answers 7

Reset to default
7

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, it will be shorter:

public static List<String> findWithPrefixJava8(List<String> list, String prefix) {
    return list.stream()
               .filter(str -> str.startsWith(prefix))
               .collect(Collectors.toList());
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

soz mate, I didn't see ur answer before posting mine,
It would be better, if I could use java 8. But for comparability reasons, I have to go with java 7.
3

well you could always use the startsWith(String s) method from String class.

e.g.

for(String s : list){
 if(s.startsWith(a)){
    System.out.println(s);
 }
}
Improve this answer

Comments

3

If you want to go through the list and pull all the strings which start with 1.1, then, using startsWith(String subString) should do what you need. You could use Java 8 Collection.parallelStream().forEach...

If, on the other hand, you want to do multiple searches, each time seeing which string starts with a different sub string (starting with being key here), you could take a look at suffix trees.

The suffix tree will index all your strings in a tree like manner. This way, you can search the tree, starting from the root node and then, once that you will have found the node which satisfies your condition, you simply keep going through it's children to get the strings.

                root
              / |  \
             1  2   3
          / |
         .  0
    /   |
   1    2
   |    |
   [1.1] [1.2]

The values in square brackets, denote where is the substring found, which in your case, would consist of the entire string.

Improve this answer

3 Comments

Thanks, this a really good idea. But my implementation list is not that large. I will use your approach in future for large lists.
That picture is a a suffix tree for what input strings?
@StefanPochmann: The complete input strings would be 1.1 and 1.2. Other substrings which are in the list would include 10, 1, 2 and 3
2

Hey as you want some optimized solution so you can try this :

  1. sort the list with help of Collections.sort(list);
  2. find for first matching string with help of binary search and make flag that string with this prefix found.
  3. now if next string doesnot match this prefix that means no next string of list will match this prefix as we have 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 doubt in code

Improve this answer

1 Comment

All that is left to do is use binary search instead of linear search to find the first element.
1

Here's an idea but I don't know if it is efficient enough.How about concatenating all the elements in a way so that you can find out which item was with: for example :

{0:1.1.2.4},{1:1.2.1.3},.....

then run a regex query over the string that returns all sub-strings that starts with a { and ends with a } and starts with 1.1 .You can define a named group to contain the index number so that you'll have all the indexes in one run.

Improve this answer

3 Comments

This sounds like far more hassle than it's worth. The regexp will always have to scan the entire string, which is the thing we want to avoid.
why do you say so ? You mean using Regex for a problem like this ?
It's simply the wrong tool in this scenario. Concatenating elements is brutally expensive with a large list and scanning through the entire list (again!) is unnecessary if you can sort it. That's of course without going into how easy it is to get the regexp wrong.
1

Does it have to be an ArrayList? Can you put the strings into a NavigableSet like a TreeSet:

TreeSet<String> strings = ...;

Set<String> startWith1_1 = strings.subSet("1.1", "1.2");
Improve this answer

Comments

1 
List<String> result=new ArrayList<String>():
for(String s : list){
 if(s.startsWith("1.1")){
    result.add(s);
 }
}
for(String s : list){
System.out.println(s);
}
Improve this answer

2 Comments

You might want to pass s as an argument to result.add(). Also, why aren't you doing the print statement in the first loop?
this is why values of list can be iterated else where even in different class or different package too.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.