Intersección de dos cadenas en Java

Necesita una función Java para encontrar la intersección de dos cadenas. es decir, caracteres comunes a las cadenas.

Ejemplo:

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

Usando HashSet :

 HashSet h1 = new HashSet(), h2 = new HashSet(); 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]); 

Esto es O(m + n) , que es asintóticamente óptimo.

Extrae los personajes

 String.toCharArray 

Ponlos en un conjunto Encuentra la intersección

 Set.retainAll 

El enfoque más básico:

 String wordA = "Sychelless"; String wordB = "Sydney"; String common = ""; for(int i=0;i 

Más detalles sobre la respuesta de Saugata (apareció mientras escribía esto):

 public static void main(String[] args) { String s1 = "Seychelles"; String s2 = "Sydney"; Set ss1 = toSet(s1); ss1.retainAll(toSet(s2)); System.out.println(ss1); } public static Set toSet(String s) { Set ss = new HashSet(s.length()); for (char c : s.toCharArray()) ss.add(Character.valueOf(c)); return ss; } 

Creo que el algoritmo que está buscando es el problema de la subsecuencia común más larga

Encontré la misma pregunta aquí, refiérete a esto

Implementando un algoritmo eficiente para encontrar la intersección de dos cadenas

Por medio de Guava esta tarea parece mucho más fácil:

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

He usado TreeSet . Y retainAll() en TreeSet para obtener elementos coincidentes.

Oracle Doc:

 retainAll(Collection c) 

Retiene solo los elementos en este conjunto que están contenidos en la colección especificada (operación opcional).

 String s1 = new String("Sychelless"); String s2 = new String("Sydney"); Set firstSet = new TreeSet(); for(int i = 0; i < s1.length(); i++) { firstSet.add(s1.charAt(i)); } Set anotherSet = new TreeSet(); 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 

Para casos más sofisticados use el patrón de clase.