Program Java untuk menyemak String ialah Palindrome

Beberapa masalah dalam pengaturcaraan mempunyai status yang klasik. Lazimnya, tugasan sebegini adalah berkaitan dengan matematik dan mereka sangat gemar bertanya kepada pelajar kepakaran Sains Komputer, serta pencari kerja semasa temu duga. Mereka bagus kerana mereka membantu untuk menetapkan pemikiran anda dengan cara pengaturcara dengan cukup baik, serta melatihnya. Salah satu masalah tersebut ialah menyemak sama ada rentetan ialah palindrom, dan kami akan mempertimbangkannya dalam artikel ini.

Apakah palindrom dan mengapa boleh mencarinya

Palindrom ialah nombor, gabungan huruf, perkataan atau teks yang berbunyi sama dalam kedua-dua arah. Untuk meringkaskan, palindrom boleh dipanggil mana-mana set aksara yang simetri pada bahagian tengahnya. Perkataan itu berasal dari akar bahasa Yunani yang secara harfiah berasal dari "lari ke belakang" (palin adalah "sekali lagi, kembali," dan dromos, "berlari."). Palindrome dalam bahasa Jawa bermaksud sama dengan makna umum. Contoh palindrom:

• 1881
• aaqquqqaa
• pop
• tengah hari
• tahap
• Pemutar
• Gim saya
• Puan saya Adam
• Sekarang, tuan, perang telah dimenangi!

1881 ialah nombor palindrom dan yang lain ialah rentetan palindrom. Dalam artikel ini, kita akan melihat palindrom yang diwakili sebagai rentetan, tetapi beberapa algoritma agak sesuai untuk jenis palindrom lain di Jawa. Mengapa anda mungkin ingin mencari palindrom? Sebenarnya, kita tidak perlu selalu mencari palindrom dalam kehidupan seharian. Ia adalah jenis tugas yang sangat spesifik. Jika kita mengingati algoritma rentetan, lebih kerap dalam amalan, pengaturcara boleh mencari mencari subrentetan dalam rentetan, dan tidak mencari palindrom atau nombornya. Walau bagaimanapun, masalah yang berkaitan dengan palindrom mempunyai aplikasi penting. Yang pertama ialah pengaturcaraan olimpik. Mungkin terdapat tugas untuk mengenal pasti palindrom. Aplikasi kedua yang relevan untuk pengaturcara baru ialah temuduga. Pada temu bual teknikal, anda mungkin diminta untuk menulis program dengan cepat untuk memeriksa sama ada rentetan adalah palindrom, mungkin juga pada sekeping kertas. Nah, dalam sains, aplikasi paling praktikal untuk mencari palindrom ialah algoritma biologi. Menurut Wikipedia, palindromik sebatian biologi memainkan peranan penting dalam sifat pelbagai sebatian biologi.

Contoh kod algoritma Palindrom

Mari berfikir. Rentetan ialah jujukan aksara, boleh dikatakan, susunan aksara. Adalah paling logik untuk mengikuti urutan ini dari kedua-dua belah ke tengah dan membandingkan watak yang melampau. Jika sehingga kita sampai ke tengah semua watak kita akan sepadan, maka kita mempunyai palindrom. Mari cipta kaedah boolean validPalindrome(String s) untuk menyemak sama ada String ialah palindrom. Kod Java ada di sini:

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


   }

}

Dalam kaedah utama, kami menyemak rentetan palindromic "level", "cool", "Puan" dan "Sekarang, tuan, perang telah dimenangi!". Seperti yang anda lihat, yang pertama, ketiga dan keempat adalah palindrom, tetapi yang kedua tidak. Apa yang akan diberikan oleh program ini? Jadi, yang pertama adalah palindrom, yang kedua bukan. Namun, apa yang salah dengan yang ketiga dan keempat? Mengapa hasilnya palsu ? Anda mungkin sudah meneka bahawa maksudnya ialah beberapa aksara dalam rentetan ini adalah huruf besar dan beberapa huruf kecil, dan untuk Java M dan m ialah dua aksara yang berbeza. Mari kita perbaiki program untuk mengambil kira perbezaan ini. Berikut ialah program untuk menyemak sama ada rentetan ialah palindrom yang menyelesaikan masalah huruf besar dan kecil.

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


   }

}

Kali ini hasilnya lebih boleh diramalkan untuk kita: Nah…tidak dapat diramalkan. Keadaan dengan "Puan" semakin baik, tetapi bagaimana dengan palindrom kami yang panjang dan gembira "Sekarang, tuan, perang telah dimenangi!". Ia agak mudah, jika anda ingat bahawa semua ruang dan simbol tanda baca adalah sama dengan huruf untuk Java. Oleh itu, kami perlu memperbaiki algoritma kami sekali lagi untuk membetulkan kesilapan ini. Mari ajar program kami untuk mengabaikan ruang dan tanda baca. Ringkasnya, kami mengabaikan semua aksara bukan abjad angka. Berikut ialah program palindrom yang lebih baik di Jawa.

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


   }

}

Sekurang-kurangnya hasilnya adalah apa yang kami harapkan daripadanya: Mungkin, jika anda baru mula memprogram, sukar untuk anda memahami cara algoritma traversal dan perbandingan rentetan berfungsi. Sudah tentu, adalah lebih baik untuk menangani perkara ini, tetapi anda boleh menulis versi ringkas dari petikan itu melalui pelbagai aksara, yang sebenarnya adalah rentetan. Anda boleh menggunakan kaedah StringBuffer.reverse untuk menyemak sama ada rentetan ialah palindrom. Mari lakukan versi paling mudah tanpa menyemak simbol bukan abjad angka dan huruf besar dan kecil.

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


   }
}

Hasilnya adalah sama seperti dalam contoh pertama Jika anda mahu, anda boleh menambah baik program ini seperti yang kami lakukan dengan contoh pertama. Untuk mengukuhkan perkara yang anda pelajari, kami cadangkan anda menonton pelajaran video daripada Kursus Java kami