string - palabras - escribir un programa que encuentre dos cadenas introducidas por teclado que sean anagramas
¿Cuál es una manera fácil de decir si una lista de palabras son anagramas entre sí? (10)
Clasifique cada elemento (eliminando el espacio en blanco) y compárelo con el anterior. Si son todos iguales, todos son anagramas.
¿Cómo incluirías palabras que son anagramas el uno del otro?
Me hicieron esta pregunta cuando solicité mi trabajo actual.
orchestra
se puede reordenar en carthorse
con todas las letras originales usadas exactamente una vez, por lo tanto, las palabras son anagramas entre sí.
Coloque todas las letras en orden alfabético en la cadena (algoritmo de clasificación) y luego compare la cadena resultante.
-Adán
Curiosamente, el blog Fabulous Adventures In Coding de Eric Lippert trató una variación de este problema el 4 de febrero de 2009 en esta publicación .
El siguiente algoritmo debería funcionar:
Ordena las letras en cada palabra.
Ordene las listas ordenadas de letras en cada lista.
Compare cada elemento en cada lista para la igualdad.
Lo bueno es que todos vivimos en la realidad de C # de clasificación local de palabras cortas en máquinas de cuatro núcleos con oozles de memoria. :-)
Sin embargo, si tiene limitaciones de memoria y no puede tocar los datos originales y sabe que esas palabras contienen caracteres de la mitad inferior de la tabla ASCII, podría elegir un algoritmo diferente que cuente la ocurrencia de cada letra en cada una. palabra en lugar de ordenar.
También puede optar por ese algoritmo si desea hacerlo en O (N) y no le importa el uso de la memoria (un contador por cada carácter Unicode puede ser bastante caro).
Ordenar las letras y comparar (letra por letra, comparación de cuerda, ...) es lo primero que se le viene a la mente.
- compare la duración (si no es igual, no hay oportunidad)
- hacer un pequeño vector de la longitud de las cuerdas
- para cada
char
en la primera cadena encontrar apariciones de la misma en el segundo - establecer el bit para la primera aparición no establecida
- si puedes encontrar una parada con falla
Bueno, ordena las palabras en la lista.
si abc, bca, cab, cba son las entradas, entonces la lista ordenada será abc, abc, abc, abc.
Ahora todos sus códigos Hash son iguales. Compare los HashCodes.
public static void main(String[] args) {
String s= "abc";
String s1="cba";
char[] aArr = s.toLowerCase().toCharArray();
char[] bArr = s1.toLowerCase().toCharArray();
// An array to hold the number of occurrences of each character
int[] counts = new int[26];
for (int i = 0; i < aArr.length; i++){
counts[aArr[i]-97]++; // Increment the count of the character at respective position
counts[bArr[i]-97]--; // Decrement the count of the character at respective position
}
// If the strings are anagrams, then counts array will be full of zeros not otherwise
for (int i = 0; i<26; i++){
if (counts[i] != 0)
return false;
}
La lógica de hashcode probada para anagrama me da salida falsa
public static Boolean anagramLogic(String s,String s2){
char[] ch1 = s.toLowerCase().toCharArray();
Arrays.sort(ch1);
char[] ch2= s2.toLowerCase().toCharArray();
Arrays.sort(ch2);
return ch1.toString().hashCode()==ch2.toString().hashCode(); //wrong
}
para rectificar este código, a continuación se muestra la única opción que veo, aprecio cualquier recomendación
char[] ch1 = s.toLowerCase().toCharArray();
Arrays.sort(ch1);
char[] ch2= s2.toLowerCase().toCharArray();
Arrays.sort(ch2);
return Arrays.equals(ch1,ch2);
}