¿Cómo enumeraría las palabras que son anagramas el uno del otro?¿Cuál es una manera fácil de decir si una lista de palabras es anagrama de la otra?
Me hicieron esta pregunta cuando solicité mi trabajo actual.
orchestra se pueden reordenar en carthorse con todas las letras originales utilizadas 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.
-Adam
Sí, eso es más o menos lo que se me ocurrió ... ¡También conseguí el trabajo! – jqs
Hay un algoritmo alternativo que implica contar los caracteres en cada palabra. Es más rápido, pero será más caro para las palabras Unicode. –
Lo había considerado, pero luego tienes que comparar las matrices de conteo de letras resultantes, los hashes, o de lo contrario, para anagramas cortos mi algoritmo es probablemente más rápido, pero para anagramas más grandes las probabilidades son buenas, el tuyo sería más rápido. Sería una prueba interesante ... –
Ordene cada elemento (eliminando el espacio en blanco) y compárelo con el anterior. Si son todos iguales, todos son anagramas.
Eliminar puntuación también – dmckee
puntuación Puedo entender, para palabras con un apostrohphe, pero espacios? No conozco muchas palabras con espacios en ellas ... Creo que por el simple hecho de hacer un ejercicio como este, puedes asumir que las palabras solo contienen letras. – ninesided
Cuando se presentan como acertijos, los anagramas se suelen dividir en frases enteras. Entonces, escribe la rutina para ser robusto. – dmckee
Ordenar las letras y comparar (letra por letra, comparación de cadenas, ...) son las primeras cosas que viene a la mente.
El siguiente algoritmo debería funcionar:
Ordenar las letras de cada palabra.
Ordene las listas ordenadas de letras en cada lista.
Compara cada elemento en cada lista para la igualdad.
Una vez que las listas de letras están ordenadas, puede comparar la primera con la última en lugar de comparar cada una. Si el primero es el mismo que el anterior, entonces todos son iguales. –
@EricNess ¿Estás seguro de eso? Considere la entrada: "abbc" y "abcc". Misma longitud, mis primeros y últimos personajes ... O tal vez malinterpreté tu comentario. – levigroker
Curiosamente, Eric Lippert's Fabulous Adventures In Coding Blog tratado con una variación de este mismo problema, el 4 de febrero de 2009 en this post.
Lo bueno es que todos vivimos en la realidad C# de la ordenació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, puede elegir un algoritmo diferente que cuente la ocurrencia de cada letra en cada 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 memoria (un contador para cada carácter Unicode puede ser bastante caro).
char en la primera cadena de encontrar ocurrencias de que en la segundaclase bien las palabras de 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;
}
lógica de código hash Juzgado por 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 es la única opción que veo, apreciar ninguna recomendación
char[] ch1 = s.toLowerCase().toCharArray();
Arrays.sort(ch1);
char[] ch2= s2.toLowerCase().toCharArray();
Arrays.sort(ch2);
return Arrays.equals(ch1,ch2);
}
Hey! ¡Hacemos esta pregunta a cada programador que entrevistamos! ¡Estás estropeando las cosas para nosotros! –
@Jim En Texas: La pregunta no arruina la estrategia de su entrevista, revela que la estrategia de la entrevista es fundamentalmente defectuosa. Como elegir un mecánico basado en qué mono de color tiene. Si filtra el conocimiento a los nuevos candidatos para que siempre seleccione un mono azul, no se arruinará su estrategia de recolección mecánica. Lo revela como la no estrategia como defectuosa por el hecho de que puede ser roto por personas sin ningún conocimiento de programación. –
Me resulta difícil imaginar a 'personas sin ningún conocimiento de programación' ser capaces de pararse frente a una pizarra y escribir un programa para detectar anagramas. Esta es realmente una gran pregunta de pantalla inicial por muchas razones. Y realmente, si un candidato está lo suficientemente interesado como para haber leído esta pregunta SO, entonces ¡eso es algo bueno! –