Trova le sottostringhe che sono palindromi in Java

1. Panoramica

In questo rapido tutorial, esamineremo diversi approcci per trovare tutte le sottostringhe all'interno di una data stringa che sono palindromi . Noteremo anche la complessità temporale di ogni approccio.

2. Approccio a forza bruta

In questo approccio, itereremo semplicemente sulla stringa di input per trovare tutte le sottostringhe. Allo stesso tempo, controlleremo se la sottostringa è un palindromo o meno:

public Set findAllPalindromesUsingBruteForceApproach(String input) { Set palindromes = new HashSet(); for (int i = 0; i < input.length(); i++) { for (int j = i + 1; j <= input.length(); j++) { if (isPalindrome(input.substring(i, j))) { palindromes.add(input.substring(i, j)); } } } return palindromes; }

Nell'esempio sopra, confrontiamo la sottostringa con il suo inverso per vedere se è un palindromo:

private boolean isPalindrome(String input) { StringBuilder plain = new StringBuilder(input); StringBuilder reverse = plain.reverse(); return (reverse.toString()).equals(input); }

Naturalmente, possiamo facilmente scegliere tra diversi altri approcci.

La complessità temporale di questo approccio è O (n ^ 3). Sebbene questo possa essere accettabile per stringhe di input di piccole dimensioni, avremo bisogno di un approccio più efficiente se stiamo controllando i palindromi in grandi volumi di testo.

3. Approccio alla centralizzazione

L'idea nell'approccio centralizzato è di considerare ogni personaggio come il perno ed espandersi in entrambe le direzioni per trovare i palindromi .

Ci espanderemo solo se i caratteri sul lato sinistro e destro corrispondono, qualificando la stringa come un palindromo. Altrimenti, passiamo al personaggio successivo.

Vediamo una rapida dimostrazione in cui considereremo ogni personaggio come il centro di un palindromo:

public Set findAllPalindromesUsingCenter(String input) { Set palindromes = new HashSet(); for (int i = 0; i < input.length(); i++) { palindromes.addAll(findPalindromes(input, i, i + 1)); palindromes.addAll(findPalindromes(input, i, i)); } return palindromes; }

All'interno del ciclo sopra, ci espandiamo in entrambe le direzioni per ottenere l'insieme di tutti i palindromi centrati in ciascuna posizione. Troveremo palindromi di lunghezza pari e dispari chiamando il metodo findPalindromes due volte nel ciclo :

private Set findPalindromes(String input, int low, int high) { Set result = new HashSet(); while (low >= 0 && high < input.length() && input.charAt(low) == input.charAt(high)) { result.add(input.substring(low, high + 1)); low--; high++; } return result; }

La complessità temporale di questo approccio è O (n ^ 2). Questo è un miglioramento rispetto al nostro approccio basato sulla forza bruta, ma possiamo fare anche di meglio, come vedremo nella prossima sezione.

4. Algoritmo di Manacher

L'algoritmo di Manacher trova la sottostringa palindromica più lunga in tempo lineare . Useremo questo algoritmo per trovare tutte le sottostringhe che sono palindromi.

Prima di immergerci nell'algoritmo, inizializzeremo alcune variabili.

Innanzitutto, proteggeremo la stringa di input con un carattere di confine all'inizio e alla fine prima di convertire la stringa risultante in un array di caratteri:

String formattedInput = "@" + input + "#"; char inputCharArr[] = formattedInput.toCharArray();

Quindi, utilizzeremo un raggio di matrice bidimensionale con due righe: una per memorizzare le lunghezze di palindromi di lunghezza dispari e l'altra per memorizzare le lunghezze di palindromi di lunghezza pari:

int radius[][] = new int[2][input.length() + 1];

Successivamente, itereremo sull'array di input per trovare la lunghezza del palindromo centrato nella posizione i e memorizzeremo questa lunghezza nel raggio [] [] :

Set palindromes = new HashSet(); int max; for (int j = 0; j <= 1; j++) { radius[j][0] = max = 0; int i = 1; while (i <= input.length()) { palindromes.add(Character.toString(inputCharArr[i])); while (inputCharArr[i - max - 1] == inputCharArr[i + j + max]) max++; radius[j][i] = max; int k = 1; while ((radius[j][i - k] != max - k) && (k < max)) { radius[j][i + k] = Math.min(radius[j][i - k], max - k); k++; } max = Math.max(max - k, 0); i += k; } }

Infine, attraverseremo l'array radius [] [] per calcolare le sottostringhe palindromiche centrate in ciascuna posizione:

for (int i = 1; i <= input.length(); i++) { for (int j = 0; j  0; max--) { palindromes.add(input.substring(i - max - 1, max + j + i - 1)); } } }

La complessità temporale di questo approccio è O (n).

5. conclusione

In questo breve articolo, abbiamo discusso le complessità temporali dei diversi approcci per trovare sottostringhe che sono palindromi.

Come sempre, il codice sorgente completo degli esempi è disponibile su GitHub.