Anche perché questi sono esercizi classici nelle prove d'assunzione alla google, amazon e compagnia bella..
Avevo visto un esercizio del forum (IN STILE STRINGHE DEL DNA da confrontare) e pensavo di farlo ma è rimasto bloccato lì.
Consideriamo un dizionario con delle stringhe date ad esempio di 4 come questo:
AB BA ABB BAB
Data poi una stringa casuale come questa:
ABBBABABAB
Bisogna trovare se quest'ultima data è composta dalle sole stringhe del dizionario (anche ripetute)
Nell'esempio dovrei ottenere 3 modi possibili
(ossia tre modi: ABB − BA − BA − BAB, oppure ABB − BA − BAB − AB e ABB − BAB − AB − AB )
Sempre con lo stesso dizionario, ma dando una stringa diversa tipo questa:
ABBAAAB
Ottengo 0 modi.
Un codice ricorsivo che funziona l'ho scritto ma volevo sfruttare la programmazione dinamica o, per strafare, la tecnica memoization che memorizza solo cio' che ci serve.
Testo nascosto, fai click qui per vederlo
- Codice:
#include <iostream>
#include <vector>
using namespace std;
string X;
vector < string > P;
int modi = 0;
void dfs (string s){
if (s.length () >= X.length ()){
if (s == X) modi++;
return;
}
for (int i = 0; i < P.size (); i++){
dfs (s + P[i]);
}
}
int main (){
int N;//numero di primitive
cout << "Inserisci il numero di primitive: \n";
cin >> N;
string temp;
cout << "Inserisci le primitive (separate da uno spazio): \n";
for (int i = 0; i < N; i++){
cin >> temp;
P.push_back (temp);
}
cout << "Inserisci la stringa: \n";
cin >> X;
dfs ("");
cout << "Numero: " << modi << endl;
}
Sono tornato a rompere
)
