Scoprire Anagrammi

Una stringa è l’anagramma dell’altra se è un riordino dei caratteri compaiono nell’altra.

Per esempio, 'heart' e 'earth' sono anagrammi.

Per semplicità assumiamo che le due stringhe in input hanno la stessa lunghezza e che sono fatte di simboli appartenenti alle 26 lettere, caratteri alfabetici minuscoli. Vogliamo scrivere una funzione booleana che date due stringhe ritorna True se sono una l’anagramma dell’altra..

Soluzione 1: Corrispondenze

Possiamo controllare che ogni carattere compare nella seconda stringa. Siccome vogliamo che se nella prima stringa occorrono due “a” allora anche nella seconda ne occorrono esattamente due, ovvero tutte le lettere compaiono con la stessa molteplicità in entrambe le stringhe, quando abbiamo trovato la “a” corrispondente nella seconda stringa dobbiamo “spuntarla” perché le “a” che controlleremo successivamente non devono considerarla. Lo facciamo assegnandogli il valore None. Tuttavia, siccome le stringhe in Python sono immutabili, convertiamo prima la stringa in una lista di caratteri.




Checking Off (active5)

Ognuno degli n caratteri in s1 causa una iterazione sugli n caratteri nella lista di s2. Dunque questa soluzione ha complessità temporale \(O(n^{2})\).

Soluzione 2: Ordina e Confronta

s1 e s2 sono anagrammi solo se consistono degli stessi caratteri, indipendentemente dall’ordine con cui essi compaiono. Dunque, se ordiniamo le stringhe, affinché esse siano anagrammi, dobbiamo ottenere stringhe uguali. Per ordinare in Python possiamo usare la funzione sort che funziona su liste.




Sort and Compare (active6)

A prima vista potremmo essere tentati di dire che il tempo è \(O(n)\), visto che c’è una solo iterazione su n caratteri dopo l’ordinamento. Tuttavia, come vedremo, le due chiamate Python al metodo sort hanno un costo, che come vedremo è tipicamente \(O(n^{2})\) or \(O(n\log n)\). Dunque, il costo dell’ordinamento domina. Alla fine questo algoritmo avrà lo stesso ordine di costo del processo di ordinamento.

Soluzione 3: Forza Bruta

Una tecnica di forza bruta prova ad esplorare tutte le possibili soluzioni. Per esempio, applicandolo al nostro problema, potremmo generare tutte le stringhe che usano i caratteri di s1 e poi controllare se una di queste stringhe è s2. Tuttavia, generando tutte le stringhe possibili di s1, che ha dimensione n, ci sono n possibili primi caratteri, \(n-1\) possibili secondi caratteri, \(n-2\) per il terso, e così via. Il numero totale di stringhe candidate è \(n*(n-1)*(n-2)*...*3*2*1\), che è \(n!\). Dunque il numero di tali stringhe da generare è \(n!\).

\(n!\) cresce più veloce di \(2^{n}\) quando n diventa grande. Infatti, se s1 è costituito da 20 caratteri, ci potrebbero essere \(20!=2,432,902,008,176,640,000\) possibili stringhe. Se per ogni stringa ci mettessimo 1 secondo, ci vorrebbero comunque 77,146,816,596 anni. Questa dunque non è una buona soluzione.

Soluzione 4: Conta e Confronta

Qualsiasi due anagrammi hanno lo stesso numero di a, di b, di c, e così via. Per decidere se due stringhe sono una l’anagramma dell’altra, prima contiamo il numero di occorrenze di ciascuna lettera e poi confrontiamo tali frequenze. Dal momento che sappiamo che ci sono 26 possibili caratteri, possiamo usare una lista di 26 posizioni, una per ciascun carattere. Ogni volta che scorrendo la stringa troviamo un carattere, incrementiamo il contatore corrispondente. Alla fine, se i due vettori delle frequenze sono uguali, allora le due stringhe sono una l’anagramma dell’altra.




Count and Compare (active7)

La funzione ‘ord’ dato un carattere restituisce un intero che rappresenta il codice Unicode del carattere. Tale codice è consecutivo crescente a partire da ‘a’ per i 26 caratteri.

Per ognuna delle due stringhe, la costruzione del vettore delle frequenze costa la lunghezza dela stringa e corrisponde ai primi due for. L’ultimo for costa al più 26 iterazioni. Dunque otteniamo che il numero di iterazioni totali è \(T(n)=2n+26\), ovvero \(O(n)\), lineare.

Notiamo che, sebbene questo algoritmo sia lineare, esso richiede di memorizzare le frequenze, sacrificando spazio per andare più veloce. In questo caso, il sacrificio non è grande. Le cose sarebbero state diverse se per esempio i caratteri possibili in ciascuna stringa fossero stati migliaia: per esempio, nel caso in cui le stringhe sono lunghe n, ma il numero di simboli che esse accolgono non è noto a priori e possono essere \(2^n\). In tal caso, sarebbe stato utile un dizionario.

Next Section - Sottoarray di Somma Massima