¿Cómo encontrar todas las permutaciones de una palabra dada en un texto dado?

Esta es una pregunta de la entrevista (pantalla del teléfono): escriba una función (en Java) para encontrar todas las permutaciones de una palabra dada que aparecen en un texto dado. Por ejemplo, para la palabra abc y el texto abcxyaxbcayxycab la función debe devolver abc, bca, cab .

Yo respondería esta pregunta de la siguiente manera:

  • Obviamente puedo recorrer todas las permutaciones de la palabra dada y usar una función de substring estándar. Sin embargo, puede ser difícil (para mí ahora) escribir código para generar todas las permutaciones de palabras.

  • Es más fácil recorrer todas las subcadenas de texto del tamaño de palabra, ordenar cada subcadena y compararla con la palabra dada “ordenada”. Puedo codificar tal función de inmediato.

  • Probablemente pueda modificar algún algoritmo de búsqueda de subcadenas, pero ahora no recuerdo estos algoritmos.

Como responderías esta pregunta?

Probablemente esta no sea la solución más eficiente de forma algorítmica, pero está limpia desde el punto de vista del diseño de clase. Esta solución tiene el enfoque de comparar palabras dadas “ordenadas”.

Podemos decir que una palabra es una permutación de otra si contiene las mismas letras en el mismo número. Esto significa que puede convertir la palabra de una String a un Map . Tal conversión tendrá complejidad O (n) donde n es la longitud de la String , suponiendo que las inserciones en su implementación de Map cuestan O (1).

El Map contendrá como claves todos los caracteres encontrados en la palabra y como valores las frecuencias de los caracteres.

Ejemplo . abbc se convierte en [a->1, b->2, c->1]

bacb se convierte en [a->1, b->2, c->1]

Entonces, si tiene que saber si dos palabras son una permutación de la otra, puede convertirlas en mapas y luego invocar Map.equals .

Luego debe iterar sobre la cadena de texto y aplicar la transformación a todas las subcadenas de la misma longitud de las palabras que está buscando.

Mejora propuesta por Inerdial

Este enfoque se puede mejorar actualizando el mapa de forma “rodante”.

Es decir, si coincide en el índice i=3 en el pajar de ejemplo en el OP (la subcadena xya ), el mapa será [a->1, x->1, y->1] . Al avanzar en el pajar, disminuya el recuento de caracteres para el haystack[i] e incremente el recuento para el haystack[i+needle.length()] .

(Soltando ceros para asegurarse de que Map.equals() funcione o simplemente implemente una comparación personalizada).

Mejora propuesta por Max

¿Y si también presentamos la variable matchedCharactersCnt ? Al comienzo del pajar será 0 . Cada vez que cambias tu mapa hacia el valor deseado, aumentas la variable. Cada vez que lo cambias lejos del valor deseado, reduces la variable. Cada iteración verifica si la variable es igual a la longitud de la aguja. Si es así, has encontrado una coincidencia. Sería más rápido que comparar el mapa completo cada vez.

Pseudocódigo proporcionado por Max:

 needle = "abbc" text = "abbcbbabbcaabbca" needleSize = needle.length() //Map of needle character counts targetMap = [a->1, b->2, c->1] matchedLength = 0 curMap = [a->0, b->0, c->0] //Initial map initialization for (int i=0;i 0 && curValue1 > 0 && curValue1 <= targetValue1) { matchedLength--; } curMap[haystack[i]] = curValue1 + 1; //Write to hashmap, O(1) int targetValue2 = targetMap[haystack[i+needle.length()]] //Read int curValue2 = curMap[haystack[i+needle.length()]] //Read //We are adding a beneficial character if (targetValue2 > 0 && curValue2 < targetValue2) { //If we don't need this letter at all, the amount of matched letters decreases matchedLength++; } curMap[haystack[i+needle.length()]] = curValue2 + 1; //Write if (matchedLength == needleSize) { System.out.println("Match found at: "+(i+1)); } } //Basically with 4 reads and 2 writes which are //independent of the size of the needle, //we get to the maximal possible performance: O(n) 

Para encontrar una permutación de una cadena, puede usar la teoría de números. Pero tendrá que conocer la ‘teoría’ detrás de este algoritmo por adelantado antes de poder responder la pregunta utilizando este algoritmo.

Hay un método donde puedes calcular un hash de una cadena usando números primos. Cada permutación de la misma cadena dará el mismo valor hash. La otra combinación de cadenas que no sea una permutación dará otro valor hash.

El valor hash se calcula mediante c 1 * p 1 + c 2 * p 2 + … + c n * p n donde c i es un valor único para el carácter actual en la cadena y donde p i es un primo único valor numérico para el c i char.

Aquí está la implementación.

 public class Main { static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 }; public static void main(String[] args) { final char[] text = "abcxaaabbbccyaxbcayaaaxycab" .toCharArray(); char[] abc = new char[]{'a','b','c'}; int match = val(abc); for (int i = 0; i < text.length - 2; i++) { char[] _123 = new char[]{text[i],text[i+1],text[i+2]}; if(val(_123)==match){ System.out.println(new String(_123) ); } } } static int p(char c) { return primes[(int)c - (int)'a']; } static int val(char[] cs) { return p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2]; } } 

El resultado de esto es: cabina abc bca

Debería poder hacer esto en una sola pasada. Comience construyendo un mapa que contenga todos los caracteres de la palabra que está buscando. Entonces inicialmente el mapa contiene [a, b, c] .

Ahora, revisa el texto un personaje a la vez. El ciclo se ve algo así, en pseudo-código.

 found_string = ""; for each character in text if character is in map remove character from map append character to found_string if map is empty output found_string found_string = "" add all characters back to map end if else // not a permutation of the string you're searching for refresh map with characters from found_string found_string = "" end if end for 

Si desea ocurrencias únicas, cambie el paso de salida para que agregue las cadenas encontradas a un mapa. Eso eliminará los duplicados.

Existe el problema de las palabras que contienen letras duplicadas. Si eso es un problema, haga que la clave sea la letra y el valor cuenten. ‘Eliminar’ un personaje significa disminuir su cuenta en el mapa. Si el recuento va a 0, entonces el personaje se elimina efectivamente del mapa.

El algoritmo tal como está escrito no encontrará sucesos superpuestos. Es decir, dado el texto abcba , solo encontrará abc . Si desea manejar apariciones superpuestas, puede modificar el algoritmo para que cuando encuentre una coincidencia, disminuya el índice en uno menos la longitud de la cadena encontrada.

Ese fue un rompecabezas divertido. Gracias.

Esto es lo que haría: configurar una matriz de banderas con un elemento igual a 0 o 1 para indicar si ese personaje en STR se ha emparejado

Establezca el primer resultado de la cadena RESULTADO en vacio.

para cada personaje C en TEXTO:

Establezca una matriz X igual a la longitud de STR a todos los ceros.

para cada carácter S en STR: si C es el carácter JTH en STR, y X [J] == 0, entonces configure X [J] <= 1 y agregue C a RESULTADO. Si la duración de RESULTADO es igual a STR, agregue RESULTADO a una lista de permutaciones y establezca los elementos de X [] en ceros nuevamente.

Si C no tiene ningún carácter J en STR que tenga X [J] == 0, entonces establezca los elementos de X [] en ceros nuevamente.

El segundo enfoque me parece muy elegante y debería ser perfectamente aceptable. Creo que escala en O(M * N log N) , donde N es la longitud de la palabra y M es la longitud del texto.

Puedo encontrar un algoritmo O(M) algo más complejo:

  1. Cuente la ocurrencia de cada personaje en la palabra
  2. Haga lo mismo para los primeros N caracteres (N (es decir, length(word) ) del texto
  3. Reste los dos vectores de frecuencia, produciendo subFreq
  4. Cuente el número de no-ceros en subFreq , obteniendo numDiff
  5. Si numDiff es igual a cero, hay una coincidencia
  6. Actualice subFreq y numDiff en tiempo constante al actualizar para el primer y último carácter en el texto
  7. Vaya a 5 hasta llegar al final del texto

EDITAR : ver que se han publicado varias respuestas similares. La mayoría de este algoritmo es equivalente al conteo de frecuencia de rodadura sugerido por otros. Mi humilde adición también actualiza el número de diferencias de forma continua, produciendo un algoritmo O(M+N) lugar de uno O(M*N) .

EDIT2 : Acabo de ver que Max básicamente ha sugerido esto en los comentarios, por lo que Brownie le señala.

Este código debería hacer el trabajo:

 import java.util.ArrayList; import java.util.List; public class Permutations { public static void main(String[] args) { final String word = "abc"; final String text = "abcxaaabbbccyaxbcayxycab"; List charsActuallyFound = new ArrayList(); StringBuilder match = new StringBuilder(3); for (Character c : text.toCharArray()) { if (word.contains(c.toString()) && !charsActuallyFound.contains(c)) { charsActuallyFound.add(c); match.append(c); if (match.length()==word.length()) { System.out.println(match); match = new StringBuilder(3); charsActuallyFound.clear(); } } else { match = new StringBuilder(3); charsActuallyFound.clear(); } } } } 

La lista CharsActuallyFound se utiliza para realizar un seguimiento del personaje que ya se encuentra en el bucle. Es necesario para evitar mathing “aaa” “bbb” “ccc” (agregado por mí al texto que especificó).

Después de una mayor reflexión, creo que mi código solo funciona si la palabra dada no tiene caracteres duplicados. El código de arriba se imprime correctamente

 abc bca cab 

pero si buscas la palabra “aaa”, entonces no se imprime nada, porque cada char no puede coincidir más de una vez. Inspirado en la respuesta de Jim Mischel, edito mi código, terminando con esto:

 import java.util.ArrayList; import java.util.List; public class Permutations { public static void main(String[] args) { final String text = "abcxaaabbbccyaxbcayaaaxycab"; printMatches("aaa", text); printMatches("abc", text); } private static void printMatches(String word, String text) { System.out.println("matches for "+word +" in "+text+":"); StringBuilder match = new StringBuilder(3); StringBuilder notYetFounds=new StringBuilder(word); for (Character c : text.toCharArray()) { int idx = notYetFounds.indexOf(c.toString()); if (idx!=-1) { notYetFounds.replace(idx,idx+1,""); match.append(c); if (match.length()==word.length()) { System.out.println(match); match = new StringBuilder(3); notYetFounds=new StringBuilder(word); } } else { match = new StringBuilder(3); notYetFounds=new StringBuilder(word); } } System.out.println(); } } 

Esto me da el siguiente resultado:

 matches for aaa in abcxaaabbbccyaxbcayaaaxycab: aaa aaa matches for abc in abcxaaabbbccyaxbcayaaaxycab: abc bca cab 

Hizo algún punto de referencia, el código anterior encontró 30815 coincidencias de “abc” en una cadena aleatoria de 36M en solo 4,5 segundos. Como Jim ya dijo, gracias por este rompecabezas …