Is there any way to know if an arraylist contains

Question

I have an arraylist with several items. Let's say they are: "DARK BROWN", "BLUE", "GREEN",....

Is there any way to look for if there's the string "DARK" in some of my items? I know that contains does this but it only does if the string is exactly. My idea is to look for a text that starts as one of my items but it hasn't all the last characters.

I have thougth in do a loop like:

for(int i=0;i<arraylist.size;i++){
  String s = arraylist.get(i);
  if (s.startsWith(mytext)){
   do something
  }
}

but it seems to be a very slow method because the arraylist can contain a lot of elements. Any better ideas?

EDIT

Just to be sure you understand my point. I want to know if an item of my arraylist contains an element that starts with some text and to get the complete text of that element. ArrayList.contains is a boolean. If I need to retrieve information I will have to use IndexOf or so but this function gives me null if I put "brown"

EDIT 2

This is for you auselen:

Arraylist (5000 elements or so):

• "David's cat is in his bedroom"
• "I like the moon"
• "I want to travel to Mars"
• "My ball is red"
• "They always forget about Antarctida"
• ...

I want to know if there's an element that starts with "I want to" and then retrieve the rest of the element.

Answer 1

Or you can use completly different approach. and wrap ArrayList and check upon list.add() for a match. And store it in some var for quick access. But if you have multiple values to search, then this approach is not good at all :).

Answer 2

Either do it like you have done it, or it gets much more complex. There is a search structure called "trie" , but this is complex.

You could gain a bit by having an array of a- z pointing to the start position in your sorted ArrayList of the first letter. Then you only have to search within the words that start with the same letter.

Answer 3

it seems to be a very slow method because the arraylist can contain a lot of elements.

Like, a million?

Nov 30, 2012 10:05:20 AM test.t100.t001.ArrayListSpeed main
INFO: Creating entries.
Nov 30, 2012 10:05:21 AM test.t100.t001.ArrayListSpeed main
INFO: Searching..
Nov 30, 2012 10:05:21 AM test.t100.t001.ArrayListSpeed main
INFO: Searching 'dark' 333716
Nov 30, 2012 10:05:21 AM test.t100.t001.ArrayListSpeed main
INFO: Searching 'light' 333333
Nov 30, 2012 10:05:22 AM test.t100.t001.ArrayListSpeed main
INFO: Searching 'plain' 332951

Code

package test.t100.t001;

import java.util.ArrayList;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;

public class ArrayListSpeed {

    public static String[] PREFIX = {"Dark ", "Light ", "Plain "};
    public static String[] COLOR = {"Red", "Green", "Blue"};

    public static String getColor(Random r) {
        int val = r.nextInt(COLOR.length);
        return COLOR[val];
    }

    public static String getPrefix(Random r) {
        int val = r.nextInt(PREFIX.length);
        return PREFIX[val];
    }

    public static int countPrefixes(ArrayList<String> list, String prefix) {
        int count = 0;
        for (String val : list) {
            if (val.toLowerCase().startsWith(prefix.toLowerCase())) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Logger logger = Logger.getAnonymousLogger();
        ArrayList<String> list = new ArrayList<String>();
        Random r = new Random();
        logger.log(Level.INFO, "Creating entries.");
        for (int ii=0; ii<1000000; ii++) {
            list.add( getPrefix(r) + getColor(r) );
        }
        logger.log(Level.INFO, "Searching..");
        logger.log(Level.INFO, 
                "Searching 'dark' " + countPrefixes(list,"dark"));
        logger.log(Level.INFO, 
                "Searching 'light' " + countPrefixes(list,"light"));
        logger.log(Level.INFO, 
                "Searching 'plain' " + countPrefixes(list,"plain"));
    } 
}

Answer 4

Here is an example of a function you could use with getting each item. The speed of this is not really an increase. Due to this being an arraylist there is not really a good way to do this. There are better data structures for searching for parts of a string.

    public class RegionMatchesDemo {
public static void main(String[] args) {
    String searchMe = "Green Eggs and Ham";
    String findMe = "Eggs";
    int searchMeLength = searchMe.length();
    int findMeLength = findMe.length();
    boolean foundIt = false;
    for (int i = 0; 
         i <= (searchMeLength - findMeLength);
         i++) {
       if (searchMe.regionMatches(i, findMe, 0, findMeLength)) {
          foundIt = true;
          System.out.println(searchMe.substring(i, i + findMeLength));
          break;
       }
    }
    if (!foundIt)
        System.out.println("No match found.");
  }
}

Answer 5

Keep the strings in a sorted(!) array and use binarysearch to find the insertion point of your prefix. The matches will be at that point, if at all.

Performance if this is O(log n) instead of O(n), you should find it to be much faster, in particular for large data sets.

import static org.junit.Assert.assertEquals;
import java.util.Arrays;
import org.junit.Test;

public class ContainsPrefix {

    public static String findWithPrefix(String[] data, String prefix) {
        int n = Arrays.binarySearch(data, prefix);
        if (n < 0) n = -1 - n;
        // Loop here if you want to find all matches ...
        if (!data[n].startsWith(prefix)) return null;
        return data[n];
    }


    @Test
    public void shouldFindStringWithPrefix() {
        String[] data = { //
                "David's cat is in his bedroom", //
                "I like the moon", //
                "I want to travel to Mars", //
                "My ball is red", //
                "They always forget about Antarctida", //
                "..." //
            };
        Arrays.sort(data);
        String found = findWithPrefix(data, "I want to");
        assertEquals("I want to travel to Mars", found);

    }

}