Intersection of two strings in Java

Question

Need a Java function to find intersection of two strings. i.e. characters common to the strings.

Example:

String s1 = new String("Sychelless");
String s2 = new String("Sydney");

Solution 1

Using HashSet<Character>:

HashSet<Character> h1 = new HashSet<Character>(), h2 = new HashSet<Character>();
for(int i = 0; i < s1.length(); i++)                                            
{
  h1.add(s1.charAt(i));
}
for(int i = 0; i < s2.length(); i++)
{
  h2.add(s2.charAt(i));
}
h1.retainAll(h2);
Character[] res = h1.toArray(new Character[0]);

This is O(m + n), which is asymptotically optimal.

Solution 2

Extract the characters

String.toCharArray

Put them in a Set Find the intersection

Set.retainAll

Solution 3

Most basic approach:

String wordA = "Sychelless";  
String wordB = "Sydney";  
String common = "";  

for(int i=0;i<wordA.length();i++){  
    for(int j=0;j<wordB.length();j++){  
        if(wordA.charAt(i)==wordB.charAt(j)){  
            common += wordA.charAt(i)+" ";  
            break;
        }  
    }  
}  
System.out.println("common is: "+common);  

Solution 4

More detail on saugata's response (appeared while I was writing this): -

public static void main(String[] args) {
    String s1 = "Seychelles";
    String s2 = "Sydney";
    Set<Character> ss1 = toSet(s1);
    ss1.retainAll(toSet(s2));
    System.out.println(ss1);
}

public static Set<Character> toSet(String s) {
    Set<Character> ss = new HashSet<Character>(s.length());
    for (char c : s.toCharArray())
        ss.add(Character.valueOf(c));
    return ss;
}

Solution 5

I think the algorithm you are looking for is the problem of the longest common subsequence

View more solutions