compare 2 strings, see if they are containing common items or not

Question

say i have 2 strings, Boolean hasName = false;

String employeeNames = "lee,anne,peter,sam,paul";
String managerNames = "ken,lee,sue,tim,alex";

so, what s the best way to iterate through 2 strings and find out both strings contains "lee", then i can set

hasName = true;

these are just a simple sample.. i dont want answer such as employeeNames.contains("lee") or something like that, because my data in real product are all dynamic and can be very long string...i wont know what i am getting, but as soon as i received 2 strings, i need to find out they r contianning at least one common item or not... what is the best way to this algrothoim? one more thing , the items in string all separete by "," so is there anything i can do ? thanks

What have you tried? Have you checked out the String API for useful functions? http://docs.oracle.com/javase/7/docs/api/ — Kevin Workman, Jan 30 '14 at 15:39
An obvious way would be to split them on the comma, stick the result in `Set`s, and compute the [intersection](http://stackoverflow.com/questions/7574311/efficiently-compute-intersection-of-two-sets-in-java) — NullUserException, Jan 30 '14 at 15:43

score 2 · Answer 1 · answered Jan 30 '14 at 15:53

You can use the de-duplicating property of Sets to compare the contents of your two lists of names :

public static boolean hasNames(String s1, String s2) {
    List<String> s1List = Arrays.asList(s1.split(","));
    List<String> s2List = Arrays.asList(s2.split(","));
    HashSet<String> names = new HashSet<>(s1List);
    names.addAll(s2List);
    return names.size() < s1List.size() + s2List.size();
}

Explanation : if the names are different in both lists, they will all be added to the set, so the size of the set will be equal to the sum of both lists. However, if they have one or more common terms, the set will wipe them away and therefore contain less elements than the sum of the two lists.

Plus, HashSets are using hashcodes, which makes them much faster than using List's contains(), which is in O(N).

Alessio · Accepted Answer · 2014-01-30T16:17:56.690

1

This has complexity O(N*M), where N and M are the number of strings in the two strings

public Boolean hasNames(String s1, String s2){
    List<String> s1List = Arrays.asList(s1.split(","));
    List<String> s2List = Arrays.asList(s2.split(","));

    for(String s : s1List)
        if(s2List.indexOf(s)>=0)
            return true;
    for(String s : s2List)
        if(s1List.indexOf(s)>=0)
            return true;
    return false;
}

Another option

public Boolean hasNames(String s1, String s2){
    Set<String> s1Set = new HashSet<String>();
    List<String> s2List = Arrays.asList(s2.split(","));
    for(String s : s1.split(","))
        s1Set.add(s);
    s1Set.retainAll(s2List);
    return !s1Set.isEmpty();
}

edited Jan 30 '14 at 16:17

answered Jan 30 '14 at 15:44

Alessio

2,018
25
26

Since `indexOf` iterates over list, actual complexity is O(M*N). – Alexei Kaigorodov Jan 30 '14 at 15:52
in which case? it's better to use the costructor you used and then use the isEmpty()? EDIT: I found the problem, let met edit it – Alessio Jan 30 '14 at 16:15

Drifter64 · Answer 3 · 2014-01-30T15:54:30.350

1

Try something like this:

public static boolean hasName()
{
    boolean value = false;
    String[] empArr = employeeNames.split(",");
    String[] manArr = managerNames.split(",");

    for (int i = 0; i < empArr.length; i++)
    {
        String s = empArr[i];

        for int j = 0, j < manArr.length; j++)
        {
            String t = manArr[j];
            if (s.equals(t)) { value = true; }
        }
    }

    return value;
}

This loops through both lists and tries to find something that is both in the first and second list!

edited Jan 30 '14 at 15:54

answered Jan 30 '14 at 15:48

Drifter64

1,103
3
11
30

This has complexity N*M, not N+M – Alessio Jan 30 '14 at 15:49
I did not make any claim as to the time complexity. The solution is easy to understand. Also a linear complexity is not possible with this algorithm, since you need to check every value in a list against every value in the other list. – Drifter64 Jan 30 '14 at 15:52

score 1 · Answer 4 · answered Jan 30 '14 at 15:56

Use StringTokenizer Class to split all words in the first string and insert them all in a HashSet. For the second string, check if any word is in the hashSet or not. The complexity of this code is O(max(N, M)) ~= O(N).

String employeeNames = "lee,anne,peter,sam,paul";
String managerNames = "ken,lee,sue,tim,alex";
boolean hasName = false;

HashSet<String> hash = new HashSet<>();
StringTokenizer st1 = new StringTokenizer(employeeNames);
while (st1.hasMoreTokens()) {
    hash.add(st1.nextToken());
}

StringTokenizer st2 = new StringTokenizer(managerNames);
while (st2.hasMoreTokens()) {
    if (hash.contains(st2.nextToken())) {
        hasName = true;
        break;
    }
}

Alexei Kaigorodov · Answer 5 · 2014-01-30T16:04:30.417

1

public Boolean hasNames(String s1, String s2){
  List<String> s1List = Arrays.asList(s1.split(","));
  List<String> s2List = Arrays.asList(s2.split(","));
  HashSet set=new HashSet(s1List);
  set.retainAll(s2List);
  return !set.isEmpty();
}

Complexity is O(M*ln(N)).

edited Jan 30 '14 at 16:04

answered Jan 30 '14 at 15:56

Alexei Kaigorodov

13,189
1
21
38

compare 2 strings, see if they are containing common items or not

5 Answers5