Ho pensato a questo problema per un po ', e posso trovare solo una soluzione ricorsiva, ma sento che esiste un modo di programmazione dinamico per farlo, ma non riesco a capirlo. È un problema famoso che non conosco?
Q: dati una stringa e un pattern, restituisci il numero di modi univoci di corrispondenza delle lettere del pattern (in ordine) con la stringa.
Chiarimento: Per trovare una corrispondenza, si prende il primo carattere del pattern, si trova il primo carattere corrispondente nella stringa, quindi si prende il secondo carattere del pattern e si combina con il primo carattere corrispondente della stringa che è DOPO il carattere precedentemente abbinato.
Esempio 1 (4 partite):
Stringa: DABBCDDE
Pattern: ABD
Possibili modi (i caratteri in grassetto sono dove il modello è abbinato alla stringa):
- D AB BC D DE
- D A B B C D DE
- D AB BCD D E
- D A B B CD D E
Esempio 2 (0 corrispondenze):
Stringa: ABC
Pattern: BCA
(Corrispondi a B, C e sei alla fine della stringa, NON puoi tornare indietro e trovare corrispondenze con i personaggi precedenti)
Con l'approccio ricorsivo, ho un metodo che tiene traccia di quale indice sono sulla stringa ( sIndex ) e del pattern ( pIndex ) . Se stringa [sIndex] corrisponde al modello [pIndex], chiamiamo di nuovo il metodo e aumentiamo sIndex e pIndex. Altrimenti, basta aumentare sIndex e riprovare a trovare una corrispondenza. Il metodo restituisce il numero totale perché il valore restituito delle chiamate ricorsive viene sommato. (Le corrispondenze aggiungono 1, nessuna corrispondenza aggiunge 0)
Casi di base:
-
Se pIndex è maggiore della lunghezza del pattern, restituisci 0.
-
Se sIndex è più grande della lunghezza della stringa, restituisci 1 (abbiamo trovato una corrispondenza!)
Quali altre soluzioni ci sono?