Programul Java pentru a verifica un String este un Palindrom

Unele probleme din programare au statutul de cele clasice. De obicei, astfel de sarcini sunt legate de matematică și le place foarte mult să întrebe studenții de specialități în Informatică, precum și persoanele aflate în căutarea unui loc de muncă la interviuri. Sunt bune pentru că vă ajută să vă configurați gândirea într-un mod de programator destul de bine, precum și să o antrenați. Una dintre astfel de probleme este verificarea dacă un șir este un palindrom și îl vom lua în considerare în acest articol.

Ce este un palindrom și de ce să le poți căuta

Un palindrom este un număr, o combinație de litere, un cuvânt sau un text care se citește la fel în ambele direcții. Pentru a rezuma, un palindrom poate fi numit orice set de caractere care este simetric față de mijlocul său. Cuvântul provine de la rădăcinile grecești care derivă literalmente „a alerga înapoi” (palin este „din nou, înapoi” și dromos, „alergă”). Palindrom în Java înseamnă același lucru ca în sens general. Exemple de palindroame:

• 1881
• aaqquqqaa
• pop
• Amiază
• nivel
• Rotator
• Sala mea de sport
• Doamnă, sunt Adam
• Acum, domnule, s-a câștigat un război!

1881 este un număr palindrom, iar celelalte sunt șiruri de palindrom. În acest articol, ne vom uita la palindromurile care sunt reprezentate ca șiruri de caractere, dar unii algoritmi sunt destul de aplicabili altor tipuri de palindromuri în Java. De ce ai vrea să cauți palindroame? De fapt, nu trebuie să căutăm adesea palindromuri în viața de zi cu zi. Este un fel de sarcină foarte specifică. Dacă ne amintim de algoritmi de șir, mai des în practică, programatorii pot găsi căutarea unui subșir într-un șir, și nu căutarea palindromilor sau a numărului lor. Problemele legate de palindrom au însă aplicații importante. Prima este programarea olimpiadelor. Ar putea exista sarcini de identificare a palindromilor. A doua aplicație care este relevantă pentru programatorii începători este interviul. La un interviu tehnic, s-ar putea să vi se ceară să scrieți rapid un program pentru a verifica dacă un șir este palindrom, poate chiar pe o bucată de hârtie. Ei bine, în știință, cea mai practică aplicație a găsirii palindromilor sunt algoritmii biologici. Potrivit Wikipedia, palindromicitatea compușilor biologici joacă un rol important în proprietățile diferiților compuși biologici.

Exemplu de cod al algoritmului palindrom

Să ne gândim. Un șir este o secvență de caractere, s-ar putea spune, o matrice de caractere. Cel mai logic ar fi să urmați această secvență de pe ambele părți până la mijloc și să comparați personajele extreme. Dacă până ajungem la mijloc toate personajele noastre se vor potrivi, atunci avem un palindrom. Să creăm o metodă booleană validPalindrom(String s) pentru a verifica dacă String este palindrom. Codul Java este aici:

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);


   }

}

În metoda principală, verificăm șirurile palindromice „nivel”, „cool”, „Doamnă” și „Acum, domnule, s-a câștigat un război!”. După cum puteți vedea, primul, al treilea și al patrulea sunt palindromuri, dar al doilea nu este. Ce va oferi programul? Deci, primul este un palindrom, al doilea nu. Totuși, ce este în neregulă cu a treia și a patra? De ce rezultatul este fals ? Probabil ați ghicit deja că ideea este că unele caractere din acest șir sunt majuscule, iar altele sunt litere mici, iar pentru Java M și m sunt două caractere diferite. Să îmbunătățim programul pentru a ține cont de această diferență. Iată un program pentru a verifica dacă un șir este un palindrom care rezolvă problemele cu litere mari și mici.

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);


   }

}

De data aceasta rezultatul este mai previzibil pentru noi: Ei bine... nu tocmai previzibil. Situația cu „Doamna” este din ce în ce mai bună, dar cu palindromul nostru lung și fericit „Acum, domnule, s-a câștigat un război!”. Este destul de ușor, dacă vă amintiți că toate spațiile și simbolurile de punctuație sunt la fel ca literele pentru Java. Așa că trebuie să ne îmbunătățim din nou algoritmul pentru a corecta această ignorare. Să învățăm programul nostru să ignore spațiile și semnele de punctuație. Pur și simplu, ignorăm toate caracterele non-alfanumerice. Iată programul îmbunătățit de palindrom în 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);


   }

}

Cel puțin rezultatul este ceea ce ne așteptam de la el: Poate că, dacă abia începeți să programați, vă este dificil să înțelegeți cum funcționează algoritmii de traversare și comparare a șirurilor. Desigur, este mai bine să te ocupi de asta, dar poți scrie o versiune simplificată a trecerii prin matricea de caractere, care de fapt este un șir. Puteți utiliza metoda StringBuffer.reverse pentru a verifica dacă un șir este un palindrom. Să facem cea mai simplă versiune fără a verifica simbolurile non-alfanumerice și litere mari și mici.

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);


   }
}

Rezultatul este același ca în primul exemplu Dacă doriți, puteți îmbunătăți acest program, așa cum am făcut cu primul exemplu. Pentru a consolida ceea ce ați învățat, vă sugerăm să urmăriți o lecție video de la Cursul nostru Java