Carattere spurio HW8

Question

Per effettuare la traduzione, ho creato una funzione che data una stringa, restituisce una lista di tutti i possibili anagrammi.

Avevo pensato quindi di vedere se la specifica sequenza del testo fosse in questa lista per poi, in caso, sostituirla.

Con il carattere spurio però questo non è possibile, non mi vengono in mente soluzioni per evitare questo problema.

Answer 1

Per trovare gli anagrammi con il carattere spurio potresti ciclare tutta la lunghezza della stringa ( quindi parti da 0 e arrivi alla lunghezza della stringa) e controllare il pezzo di stringa, che va dall'indice corrente, all'indice corrente + la lunghezza della chiave + 1, in questo modo dovresti ritrovarti una sottostringa che ha lunghezza della chiave + 1.
Poi controlli se ogni carattere nella chiave è presente nella sottostringa e nel caso contrario non è un anagramma. Invece se tutti i caratteri della chiave sono presenti nella sottostringa allora significa che questa sottostringa è un "quasi anagramma" della chiave.
Una volta che sai che quello è un anagramma, allora sostituisci la stessa sottostringa con il valore.
Ricorda che una chiave può avere anche due caratteri uguali, ad esempio "nana" non è il quasi anagramma di "nannc", quindi per controllare ciò ti conviene rimuovere il carattere dal testo ogni volta che sai che è presente nella chiave.

Comments

Però in questo modo devo scorrere tutto il testo con la prima chiave fino a quando non trovo più "quasi anagrammi" e in quel caso passare alla seconda, alla terza ecc...?

---

Vins, il ricorda che hai messo alla fine mi ha aiutato a risolvere dei test che andavano in errore. Grazie!

---

Questo procedimento lo devi fare per ogni chiave, poi ad ogni sostituzione otterrai un nuovo testo che di nuovo dovrai scorrere per ogni chiave, altrimenti rischi di perdere alcuni risultati.

---

Quindi ogni volta che effettuo una sostituzione con qualsiasi chiave, devo tornare alla prima? Così però i tempi non aumentano di molto?

---

Ogni volta che torna True la funzione di confronto, tu sostituisci e richiami ricorsivamente la funzione sulla sottostringa che hai appena ottenuto

---

Vedi la lezione sugli alberi di gioco, tu hai la prima stringa encrypted_text, per ogni chiave la scorri tutta e trovi tutte le possibili sostituzioni per quella chiave, ogni sostituzione che farai rappresenterà una foglia.
Ogni foglia dovrai controllarla di nuovo per ogni chiave per vedere se è un nodo che genera altre foglie e così via via ricorsivamente, finché non avrai più nodi ma solo foglie.
Alla fine devi raccogliere tutte le foglie e restituire in un set solo quelle più corte.

Esempio: ASTRONAUT-FLYING-CYRCUS, puoi sostituire ASTRON con TUR(da sorta: tur) ed ottenere TURAUT-FLYING-CYRCUS (nuova foglia da controllare), ma scorrendo di una posizione sulla stringa puoi sostituire anche STRONA con TUR(sempre da sorta: tur) ed ottenere ATURUT-FLYING-CYRCUS (altra foglia da controllare) e così via, questo solo per la prima chiave.

---

E come capisco quando sono arrivato al caso 0 della funzione ricorsiva?

---

Il caso 0 ce lo hai quando non hai più sottostringhe modificate da passare alla funzione ricorsiva per controllo, cioè quando, applicando tutte le chiavi, non trovi più quasi-anagrammi in nessuna delle stringhe in ingresso.

Answer 2

Seguendo il tuo ragionamento dovresti, data la sequenza da decifrare, eliminare di volta in volta un carattere e poi controllare se è un anagramma, ma occhio all'efficienza.

Answer 3

Ti consiglio di creare una funzione a parte che compara due stringhe e ritorna True o False se le Stringhe sono QuasiAnagrammi o meno