Alcuni problemi nella programmazione hanno lo status di quelli classici. Tipicamente, tali compiti sono legati alla matematica e sono molto affezionati a chiedere agli studenti delle specialità di Informatica, così come alle persone in cerca di lavoro durante i colloqui. Sono buoni perché aiutano a impostare abbastanza bene il tuo pensiero in un modo programmatore, oltre ad allenarlo. Uno di questi problemi è verificare se una stringa è un palindromo e lo considereremo in questo articolo.
Cos'è un palindromo e perché saperli cercare
Un palindromo è un numero, una combinazione di lettere, una parola o un testo che si legge allo stesso modo in entrambe le direzioni. Per riassumere, un palindromo può essere chiamato qualsiasi insieme di caratteri simmetrico rispetto al suo centro. La parola deriva dalle radici greche che derivano letteralmente "correre indietro" (palin è "di nuovo, indietro" e dromos, "correre"). Palindromo in Java significa lo stesso significato generale. Esempi di palindromi:
1881
aaqquqqaa
pop
Mezzogiorno
livello
Rotatore
La mia palestra
Signora io sono Adamo
Ora, signore, una guerra è vinta!
1881 è un numero palindromo e gli altri sono stringhe palindrome. In questo articolo, esamineremo i palindromi rappresentati come stringhe, ma alcuni algoritmi sono abbastanza applicabili ad altri tipi di palindromi in Java. Perché potresti voler cercare i palindromi? In effetti, non dobbiamo spesso cercare i palindromi nella vita di tutti i giorni. È una specie di compito molto specifico. Se ricordiamo gli algoritmi di stringa, più spesso in pratica, i programmatori possono trovare la ricerca di una sottostringa in una stringa e non la ricerca di palindromi o del loro numero. Tuttavia, i problemi relativi ai palindromi hanno importanti applicazioni. Il primo è la programmazione delle Olimpiadi. Potrebbero esserci compiti per identificare i palindromi. La seconda applicazione rilevante per i programmatori alle prime armi è l'intervista. In un colloquio tecnico, ti potrebbe essere chiesto di scrivere rapidamente un programma per verificare se una stringa è palindromo, magari anche su un pezzo di carta. Ebbene, nella scienza, l'applicazione più pratica per trovare i palindromi sono gli algoritmi biologici. Secondo Wikipedia, la palindromicità dei composti biologici gioca un ruolo importante nelle proprietà di vari composti biologici.
Esempio di codice dell'algoritmo palindromo
Pensiamo. Una stringa è una sequenza di caratteri, si potrebbe dire, un array di caratteri. Sarebbe molto logico seguire questa sequenza da entrambi i lati fino al centro e confrontare i caratteri estremi. Se fino a quando non raggiungiamo la metà tutti i nostri caratteri combaciano, allora abbiamo un palindromo. Creiamo un metodo booleano validPalindrome(String s) per verificare se String è palindromo. Il codice Java è qui:
public class PalindromeTest1 {
//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Nel metodo principale, controlliamo le stringhe palindromiche "level", "cool", "Madam" e "Ora, signore, una guerra è vinta!". Come puoi vedere, il primo, il terzo e il quarto sono palindromi, ma il secondo no. Cosa darà il programma?
il livello è palindromo? vero è cool un palindromo? falso Madam è un palindromo? falso è Ora, signore, una guerra è vinta! un palindromo? falso
Quindi, il primo è un palindromo, il secondo no. Tuttavia, cosa c'è di sbagliato nel terzo e nel quarto? Perché il risultato è falso ? Probabilmente hai già intuito che il punto è che alcuni caratteri in questa stringa sono maiuscoli e altri minuscoli, e per Java M e m sono due caratteri diversi. Miglioriamo il programma per tener conto di questa differenza. Ecco un programma per verificare se una stringa è un palindromo che risolve problemi di lettere maiuscole e minuscole.
public class PalindromeTest2 {
//lowercase and uppercase characters should be treated the same:
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Questa volta il risultato è più prevedibile per noi:
il livello è palindromo? vero è cool un palindromo? falso Madam è un palindromo? vero è Ora, signore, una guerra è vinta! un palindromo? falso
Beh... non esattamente prevedibile. La situazione con "Madam" sta migliorando, ma con il nostro lungo e felice palindromo "Ora, signore, una guerra è vinta!". È abbastanza facile, se ricordi che tutti gli spazi ei simboli di punteggiatura sono gli stessi delle lettere per Java. Quindi dobbiamo migliorare di nuovo il nostro algoritmo per correggere questa svista. Insegniamo al nostro programma a ignorare gli spazi e la punteggiatura. In poche parole, ignoriamo tutti i caratteri non alfanumerici. Ecco il programma palindromo migliorato in Java.
public class PalindromeTest3 {
//in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
private static boolean isAlphanumeric(char c) {
return Character.isAlphabetic(c) || Character.isDigit(c);
}
public static boolean validPalindromeIgnorePunctuation(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
// skip chars we should ignore
while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
// overskipped -> nothing left to validate
if (i >= j) return true;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindromeIgnorePunctuation(s1);
boolean b2 = validPalindromeIgnorePunctuation(s2);
boolean b3 = validPalindromeIgnorePunctuation(s3);
boolean b4 = validPalindromeIgnorePunctuation(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Almeno il risultato è quello che ci aspettavamo da esso:
il livello è palindromo? vero è cool un palindromo? falso Madam è un palindromo? vero è Ora, signore, una guerra è vinta! un palindromo? VERO
Forse, se stai appena iniziando a programmare, ti è difficile capire come funzionano gli algoritmi di attraversamento delle stringhe e confronto. Certo, è meglio occuparsene, ma puoi scrivere una versione semplificata del passaggio stesso attraverso l'array di caratteri, che in realtà è una stringa. È possibile utilizzare il metodo StringBuffer.reverse per verificare se una stringa è un palindromo. Facciamo la versione più semplice senza controllare i simboli non alfanumerici e le lettere maiuscole e minuscole.
public class PalindromeTest5 {
public static boolean validPalindrome(String s) {
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
String data = buffer.toString();
if (s.equals(data)) {
return true;
}
return false;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
Il risultato è lo stesso del primo esempio
il livello è palindromo? vero è cool un palindromo? falso Madam è un palindromo? falso è Ora, signore, una guerra è vinta! un palindromo? falso
Se vuoi, puoi migliorare questo programma come abbiamo fatto con il primo esempio. Per rafforzare ciò che hai imparato, ti suggeriamo di guardare una lezione video dal nostro corso Java
GO TO FULL VERSION