Come trovare tutte le permutazioni di una determinata parola in un determinato testo?

Question

Questa è una domanda di intervista (schermo del telefono): scrivere una funzione (in Java) per trovare tutte le permutazioni di una determinata parola che appaiono in un determinato testo. Ad esempio, per la parola abc e il testo abcxyaxbcayxycab la funzione deve restituire abc, bca, cab.

Vorrei rispondere a questa domanda come segue:

• Ovviamente posso loop su tutte le permutazioni della parola data e utilizzare una funzione standard substring. Tuttavia potrebbe essere difficile (per me in questo momento) scrivere codice per generare tutte le permutazioni di parole.

• È più semplice eseguire il ciclo su tutte le sottostringhe di testo della dimensione della parola, ordinare ciascuna sottostringa e confrontarla con la parola data "ordinata". Posso codificare immediatamente una funzione del genere.

• Probabilmente posso modificare un algoritmo di ricerca della sottostringa ma non ricordo questi algoritmi ora.

Come risponderesti a questa domanda?

Answer 1

Questa probabilmente non è la soluzione più efficiente algoritmicamente, ma è pulita dal punto di vista del design di classe. Questa soluzione prende l'approccio di confrontare parole date "ordinate".

Possiamo dire che una parola è una permutazione di un altro se contiene le stesse lettere nello stesso numero. Ciò significa che è possibile convertire la parola da String a Map<Character,Integer>. Tale conversione avrà la complessità O (n) dove n è la lunghezza di String, presupponendo che gli inserimenti nell'implementazione Map costino O (1).

Il Map conterrà come chiavi tutti i caratteri trovati nella parola e come valori le frequenze dei caratteri.

Esempio. abbc viene convertito in [a->1, b->2, c->1]

BACB viene convertito in [a->1, b->2, c->1]

Quindi, se avete sapere se due parole sono una permutazione dell'altro, entrambi è possibile convertire in mappe e quindi richiamare Map.equals .

Quindi è necessario scorrere la stringa di testo e applicare la trasformazione a tutte le sottostringhe della stessa lunghezza delle parole che si stanno cercando.

Miglioramento proposto da Inerdial

Questo approccio può essere migliorata aggiornando la mappa in modo "rolling".

I.e. se si sta verificando l'abbinamento con l'indice i=3 nell'esempio haystack nell'OP (sottostringa xya), la mappa sarà [a->1, x->1, y->1]. Quando si avanza nel mucchio di fieno, diminuire il conteggio dei caratteri per e incrementare il conteggio per haystack[i+needle.length()].

(Dropping zeri per assicurarsi Map.equals() opere, o semplicemente l'attuazione di un confronto personalizzato.)

miglioramento proposto da Max

E se anche noi introduciamo matchedCharactersCnt variabile? All'inizio del pagliaio sarà 0. Ogni volta che cambi la mappa verso il valore desiderato, aumenti la variabile. Ogni volta che lo si cambia lontano dal valore desiderato, si decrementa la variabile. Ogni iterazione controlla se la variabile è uguale alla lunghezza dell'ago. Se lo è, hai trovato una corrispondenza. Sarebbe più veloce di confrontare la mappa completa ogni volta.

Pseudocodice fornita da 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<needle.length();i++) { 
    if (curMap.contains(haystack[i])) { 
     matchedLength++ 
     curMap[haystack[i]]++ 
    } 
} 

if (matchedLength == needleSize) { 
    System.out.println("Match found at: 0"); 
} 

//Search itself 
for (int i=0;i<haystack.length()-needle.length();i++) { 
    int targetValue1 = targetMap[haystack[i]]; //Reading from hashmap, O(1) 
    int curValue1 = curMap[haystack[i]]; //Another read 
    //If we are removing beneficial character 
    if (targetValue1 > 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) 

Answer 2

Si dovrebbe essere in grado di fare questo in un unico passaggio. Inizia creando una mappa che contenga tutti i caratteri della parola che stai cercando. Quindi inizialmente la mappa contiene [a, b, c].

Ora, passa attraverso il testo un carattere alla volta. Il ciclo assomiglia a questo, in pseudo-codice.

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 

Se si desidera occorrenze univoche, modificare il passaggio di output in modo che aggiunga le stringhe trovate a una mappa. Questo eliminerà i duplicati.

C'è il problema delle parole che contengono lettere duplicate. Se questo è un problema, fai in modo che la chiave contenga la lettera e il valore. 'Rimuovere' un personaggio significa decrementarne il conteggio nella mappa. Se il conteggio diventa 0, il personaggio viene effettivamente rimosso dalla mappa.

L'algoritmo come scritto non troverà occorrenze sovrapposte. Cioè, dato il testo abcba, troverà solo abc. Se si desidera gestire occorrenze sovrapposte, è possibile modificare l'algoritmo in modo tale che quando trova una corrispondenza, decrementa l'indice di uno meno la lunghezza della stringa trovata.

Questo è stato un puzzle divertente. Grazie.

Answer 3

Questo è quello che farei - impostare una matrice bandiera con uno elemento uguale a 0 o 1 per indicare se quel carattere in STR era stato abbinato

Impostare il primo risultato stringa risultato a svuotare.

per ciascun carattere C in TESTO:

Impostare una matrice X pari alla lunghezza di STR a tutti zeri.

per ciascun carattere S in STR: Se C è il carattere JTH in STR, e X [J] == 0, quindi impostare X [J] < = 1 e aggiungere C al risultato. Se la lunghezza di RESULT è uguale a STR, aggiungere RISULTATO a un elenco di permutazioni e impostare nuovamente gli elementi di X [] su zero.

Se C non è un carattere J in STR avente X [J] == 0, quindi impostare nuovamente gli elementi di X [] su zero.

Answer 4

Il secondo approccio mi sembra molto elegante e dovrebbe essere perfettamente accettabile. Penso che scala a O(M * N log N), dove N è la lunghezza della parola e M è la lunghezza del testo.

posso venire con un po 'più complessa O(M) algoritmo:

1. contare le occorrenze di ogni personaggio nella parola
2. fare lo stesso per la prima N (cioè length(word)) caratteri del testo
3. sottrarre i due vettori di frequenza, ottenendo subFreq
4. contare il numero di non-zero in subFreq, ottenendo numDiff
5. Se numDiff uguale a zero, c'è una corrispondenza
6. Aggiornamento subFreq e numDiff in tempo costante aggiornando per la prima e dopo-ultimo carattere nel testo
7. Vai a 5 fino a raggiungere la fine del testo

MODIFICA: vedere che sono state pubblicate diverse risposte simili. La maggior parte di questo algoritmo è equivalente al conteggio della frequenza di rotolamento suggerito da altri. La mia umile aggiunta sta anche aggiornando il numero di differenze in modo rolling, producendo un algoritmo O(M+N) anziché uno O(M*N).

EDIT2: Ho appena visto che Max ha praticamente suggerito questo nei commenti, quindi Brownie punta a lui.

Answer 5

Questo codice dovrebbe fare il lavoro:

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<Character> charsActuallyFound = new ArrayList<Character>(); 
     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 è usato per tenere traccia di carattere già trovato nel ciclo. È necessario evitare la "math" "aaa" "bbb" "ccc" (aggiunta da me al testo specificato).

Dopo un'ulteriore riflessione, penso che il mio codice funzioni solo se la parola data non ha caratteri duplicati. Il codice di cui sopra stampa correttamente

abc 
bca 
cab 

ma se seaarch per la parola "aaa", quindi non viene stampato nulla, perché ogni char non può essere eguagliata più di una volta. Ispirato da Jim Mischel risposta, posso modificare il mio codice, che termina con questo:

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

} 

Questo mi dà output seguente:

matches for aaa in abcxaaabbbccyaxbcayaaaxycab: 
aaa 
aaa 

matches for abc in abcxaaabbbccyaxbcayaaaxycab: 
abc 
bca 
cab 

fatto qualche punto di riferimento, il codice di cui sopra ha trovato 30815 partite di "abc" in una stringa casuale di 36M in soli 4,5 secondi. Come già detto Jim, grazie per questo puzzle ...

Answer 6

Per trovare una permutazione di una stringa è possibile utilizzare la teoria dei numeri. Ma dovrai conoscere in anticipo la "teoria" dietro questo algoritmo prima di poter rispondere alla domanda usando questo algoritmo.

Esiste un metodo in cui è possibile calcolare un hash di una stringa utilizzando numeri primi. Ogni permutazione della stessa stringa darà lo stesso valore di hash. Tutte le altre combinazioni di stringhe che non sono permutazioni daranno un altro valore hash.

L'hash-valore è calcolato c * p + c * p + ... + c _n * p _n dove c _i è un valore univoco per il carattere corrente nella stringa e dove p _i è un valore numero primo univoco per c _i char.

Ecco l'implementazione.

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

L'uscita di questo è: abc BCA cabina