How to check a String for multiple items in a String ArrayList

Question

I have an ArrayList and add strings that I'm checking for to it like this.

ArrayList<String> al = new ArrayList<String>();
    al.add("is");
    al.add("the");

Then I have a method that returns a match found in the String that is also in the ArrayList.

public static String getWord(String str1, ArrayList<String> list)
{
    for(int i = 0; i < list.size(); i++)
    {
        if(str1.toLowerCase().contains(list.get(i)))
        {
            return list.get(i);
        }
    }
    return false;
}

Although when I want to check a String that has more than one match it only returns the fist one that was added into the ArrayList, so

al.add("is");
al.add("the");

it would return "is"

If I add them like this

al.add("the");
al.add("is");

it would return "the"

I need a way of determining how many matches there are and returning them individually.

To extend on Raedwald's comment, you can't return `false` in a method with a declared return type of `String` — Mike Koch, Jun 25 '14 at 23:41
As Raedwald mentioned, `getWord` function will throw compilation error because its return type is `String` but you return `false` if `str1` is not in the `list` — Harry Cho, Jun 25 '14 at 23:53
how can a method with a return type of String return multiple matches from the list? — Brett Okken, Jun 26 '14 at 00:09

score 1 · Answer 1 · answered Jun 26 '14 at 01:27

Try to use Map to hold, key as the string in List and value will be count matched

public static void main(String[] args) throws Exception
{
    List<String> list = new ArrayList<String>();
    list.add("aa");
    list.add("bb");
    list.add("cc");
    list.add("dd");
    list.add("ee");
    list.add("ff");
    list.add("kk");
    list.add("ff");

    System.out.println(getWord("aabbccddeeff", list));
}

public static Map<String, Integer> getWord(String str1, List<String> list)
{
    Map<String, Integer> map = new HashMap<String, Integer>();
    Integer count = 1;

    for (String match : list)
    {
        if(str1.toLowerCase().contains(match))
        {
            if(map.containsKey(match))
            {
                count = map.get(match);
                count++;

            }
            map.put(match, count);
        }
    }

    return map;
}

Or use a MultiSet...which is the same thing under the hood. – David Ehrmann Jun 26 '14 at 05:30 — David Ehrmann, Jun 26 '14 at 05:30

score 0 · Answer 2 · answered Jun 25 '14 at 23:47

Try using another array list to hold the matches

ArrayList<String> al = new ArrayList<String>();

al.add("is");
al.add("the");
//...

ArrayList<String> result = getWord("something", a1);

// return matches individually with indexes or use indexOf...
result.get(1);
result.get(result.indexOf("something random"));


// how many matches = size of the array list
result.size();


// ...

public static ArrayList<String> getWord(String str1, ArrayList<String> list)
{

    ArrayList<String> matches = new ArrayList<String>();
    String testString = str1.toLowerCase();

    for(int i = 0; i < list.size(); i++)
    {
        if(testString.contains(list.get(i)))
        {
            matches.add(list.get(i));
        }
    }
    return matches;
}

Hopefully this helps.

score 0 · Answer 3 · edited May 23 '17 at 12:11

`O(nm)` Solution:

If your String is length m and your list is length n, the algorithm you show in your original question runs in O(mn) time complexity because it has to loop through the entire list O(n) and then search the entire string O(m).

`O(n+m)` Solution:

However, you can do much better if the String can first be separated into individual words (e.g. "The dog jumped" would give ["The", "dog", "jumped"]). In this case you can have a running time of O(m + n) by first separating your String into individual words stored in a HashSet<String>, and then searching the set for each word in the list.

E.g.

Set<String> getWords(String str, Set<String> words){  // using set removes dups

    Set<String> indvWords = getIndividualWords(str);  // O(m)
    Set<String> matchedWords = new HashSet<String>(); // O(1)      

    for(String word : words)                          // O(n)
        if(indvWords.contains(word))                  // O(1)
            matchedWords.add(word);                   // O(1) 

    return matchedWords;
}                                                     // total: O(m + n)

Of course, you would have to implement Set<String> getIndividualWords(String str) yourself, perhaps using String#split(String) with a regex pattern, e.g.:

Set<String> getIndividualWords(String str){
    return new HashSet<String>(str.split("\\W")); // split string by non words
}

score -1 · Answer 4 · edited Jun 26 '14 at 04:16

-1

public static void getWord(String str1, ArrayList<String> list)
{
    for(int i = 0; i < list.size(); i++)
    {
        if(str1.toLowerCase().contains(list.get(i)))
        {
            System.out.println(list.get(i));
        }
    }

}

edited Jun 26 '14 at 04:16

Roney Michael

3,964
5
30
45

answered Jun 26 '14 at 03:51

user3777667

1

How to check a String for multiple items in a String ArrayList

4 Answers4

O(nm) Solution:

O(n+m) Solution:

`O(nm)` Solution:

`O(n+m)` Solution: