A karakterlánc ellenőrzésére szolgáló Java program palindrom

A programozás egyes problémái a klasszikus státuszúak. Az ilyen jellegű feladatok jellemzően a matematikához kötődnek, és nagyon szívesen kérdeznek interjúkon számítástechnika szakos hallgatókat, álláskeresőket. Azért jók, mert egész jól segítik a gondolkodásodat programozói módon felállítani, és edzeni is. Az egyik ilyen probléma annak ellenőrzése, hogy egy karakterlánc palindrom-e, és ebben a cikkben ezt fogjuk megvizsgálni.

Mi az a palindrom, és miért kell keresni őket

A palindrom olyan szám, betű kombináció, szó vagy szöveg, amely mindkét irányban ugyanazt olvassa. Összefoglalva, palindromnak nevezhető minden olyan karakterkészlet, amely szimmetrikus a közepére. A szó görög gyökerekből származik, amelyek szó szerint a „visszafutás” szóból származnak (palin jelentése „újra, vissza”, a dromos pedig „futás”. A palindrom a Java nyelven ugyanazt jelenti, mint az általános jelentésben. Példák palindromokra:

• 1881
• aaqquqqaa
• pop
• Dél
• szint
• Rotátor
• Saját edzőterem
• Hölgyem Ádám vagyok
• Most, uram, megnyertük a háborút!

Az 1881 egy palindrom szám, a többi pedig palindrom húr. Ebben a cikkben olyan palindromokat fogunk megvizsgálni, amelyek karakterláncként vannak ábrázolva, de bizonyos algoritmusok teljesen alkalmazhatók a Java más típusú palindromjaira. Miért érdemes palindromokat keresni? Valójában a hétköznapokban sem kell gyakran palindromokat keresnünk. Ez egy nagyon konkrét feladat. Ha felidézzük a karakterlánc-algoritmusokat, akkor a gyakorlatban a programozók azt találják, hogy egy karakterláncban egy részkarakterláncot keresnek, nem pedig palindromokat vagy azok számát. A palindromokkal kapcsolatos problémáknak azonban fontos alkalmazásai vannak. Az első az olimpia programozása. Lehetnek feladatok a palindromák azonosítására. A második alkalmazás, amely a kezdő programozók számára releváns, az interjú. Egy műszaki interjún könnyen előfordulhat, hogy megkérnek, hogy írjon gyorsan egy programot, hogy ellenőrizze, hogy egy karakterlánc palindrom-e, esetleg még egy papírra is. Nos, a tudományban a palindromok megtalálásának legpraktikusabb alkalmazása a biológiai algoritmusok. A Wikipédia szerint a biológiai vegyületek palindromicitása fontos szerepet játszik a különféle biológiai vegyületek tulajdonságaiban.

Példa a palindrom algoritmus kódjára

Gondolkozzunk. A karakterlánc karakterek sorozata, mondhatnánk, karakterek tömbje. Az lenne a leglogikusabb, ha ezt a sorrendet mindkét oldalról középre követnénk, és összehasonlítanánk az extrém karaktereket. Ha addig, amíg el nem érjük a közepét, minden karakterünk megegyezik, akkor palindromunk van. Hozzon létre egy logikai metódust validPalindrome(String s) annak ellenőrzésére, hogy a String palindrom-e. A Java kód itt található:

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


   }

}

A fő módszerben a „level”, „cool”, „madam” és „Most, uram, megnyert egy háború!” palindromikus húrokat keresünk. Amint látja, az első, a harmadik és a negyedik palindrom, de a második nem. Mit fog adni a program? Tehát az első palindrom, a második nem. De mi a baj a harmadikkal és a negyedikkel? Miért hamis az eredmény ? Valószínűleg már sejtette, hogy a lényeg az, hogy ebben a karakterláncban egyes karakterek nagybetűk, mások pedig kisbetűk, Java esetén pedig az M és az m két különböző karakter. Javítsuk a programot, hogy figyelembe vegyük ezt a különbséget. Íme egy program annak ellenőrzésére, hogy egy karakterlánc palindrom-e, amely megoldja a kis- és nagybetűs problémákat.

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


   }

}

Ezúttal az eredmény kiszámíthatóbb számunkra: Hát… nem pontosan kiszámítható. „Asszonyom” helyzete egyre jobb, de mi van a hosszú és boldog palindromunkkal „Most, uram, megnyert egy háború!”. Ez nagyon egyszerű, ha emlékszel arra, hogy minden szóköz és írásjel megegyezik a Java betűivel. Tehát ismét javítanunk kell az algoritmusunkon, hogy kijavítsuk ezt a hibát. Tanítsuk meg programunkat a szóközök és írásjelek figyelmen kívül hagyására. Egyszerűen fogalmazva, figyelmen kívül hagyunk minden nem alfanumerikus karaktert. Itt van a továbbfejlesztett palindrom program Java nyelven.

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


   }

}

Az eredmény legalább az, amit vártunk tőle: Talán, ha most kezdi el a programozást, nehéz megértenie a karakterlánc-bejárási és összehasonlító algoritmusok működését. Természetesen jobb ezzel foglalkozni, de megírhatja a karaktertömbön keresztüli átjárás egyszerűsített változatát is, amely valójában egy karakterlánc. A StringBuffer.reverse metódussal ellenőrizheti, hogy egy karakterlánc palindrom-e. Végezzük el a legegyszerűbb verziót anélkül, hogy ellenőriznénk a nem alfanumerikus szimbólumokat, valamint a nagy- és kisbetűket.

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


   }
}

Az eredmény ugyanaz, mint a legelső példában Ha szeretné, fejlesztheti ezt a programot, ahogyan az első példában tettük. A tanultak megerősítése érdekében javasoljuk, hogy nézzen meg egy videóleckét a Java-tanfolyamról