Intersection of two strings in Java

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");

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.

Extract the characters

String.toCharArray

Put them in a Set Find the intersection

Set.retainAll

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);  

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;
}

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

Found same question here, refer this

Implementing an efficent algorithm to find the intersection of two strings

By means of Guava this task seems much easier:

String s1 = new String("Sychelless");
String s2 = new String("Sydney");
Set<String> setA = Sets.newHashSet(Splitter.fixedLength(1).split(s1));
Set<String> setB = Sets.newHashSet(Splitter.fixedLength(1).split(s2));
Sets.intersection(setA, setB);

Optimized solution:

public static String twoStrings(String s1, String s2){

    HashSet<Character> stringOne =  new HashSet<Character>(), stringTwo = new HashSet<Character>();  
    int stringOneLength = s1.length();
    int stringTwoLength = s2.length();
    for(int i=0; i<stringOneLength || i<stringTwoLength; i++) {
        if(i < stringOneLength)
            stringOne.add(s1.charAt(i));
        if(i < stringTwoLength)
            stringTwo.add(s2.charAt(i));
    }
    stringOne.retainAll(stringTwo);

    return stringOne.toString();
}

I have used TreeSet. And retainAll() in TreeSet to get matched elements.

Oracle Doc:

retainAll(Collection<?> c)

Retains only the elements in this set that are contained in the specified collection (optional operation).

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

Set<Character> firstSet = new TreeSet<Character>();
for(int i = 0; i < s1.length(); i++) {
    firstSet.add(s1.charAt(i));
}

Set<Character> anotherSet = new TreeSet<Character>();
for(int i = 0; i < s2.length(); i++) {
    anotherSet.add(s2.charAt(i));
}

firstSet.retainAll(anotherSet);
System.out.println("Matched characters are " + firstSet.toString());//print common strings

//output > Matched characters are [S, e, y]

s1.contains(s2) returns true;
s1.indexOf(s2) returns 0. 
s1.indexOf("foo") returns -1

For more sophisticated cases use class Pattern.