Chương trình Java để kiểm tra Chuỗi có phải là Palindrome không

Một số vấn đề trong lập trình có trạng thái cổ điển. Thông thường, những nhiệm vụ như vậy liên quan đến toán học và họ rất thích hỏi các sinh viên chuyên ngành Khoa học Máy tính, cũng như những người tìm việc tại các cuộc phỏng vấn. Chúng tốt vì chúng giúp thiết lập tư duy của bạn theo cách lập trình viên khá tốt, cũng như rèn luyện nó. Một trong những vấn đề như vậy là kiểm tra xem một chuỗi có phải là một palindrom hay không và chúng ta sẽ xem xét nó trong bài viết này.

Palindrome là gì và tại sao có thể tìm kiếm chúng

Palindrome là một số, tổ hợp chữ cái, từ hoặc văn bản đọc giống nhau theo cả hai hướng. Tóm lại, một bảng màu có thể được gọi là bất kỳ tập hợp ký tự nào đối xứng qua phần giữa của nó. Từ này có nguồn gốc từ tiếng Hy Lạp có nghĩa đen là "chạy lùi" (palin là "một lần nữa, quay lại" và dromos là "chạy".). Palindrome trong Java có nghĩa giống như nghĩa chung. Ví dụ về palindrome:

• 1881
• aaqquqqaa
• nhạc pop
• Buổi trưa
• mức độ
• công cụ quay vòng
• phòng tập thể dục của tôi
• Thưa bà, tôi là Adam
• Bây giờ, thưa ngài, một cuộc chiến đã thắng!

1881 là một số đối xứng và các số khác là chuỗi đối xứng. Trong bài viết này, chúng ta sẽ xem xét các palindrome được biểu diễn dưới dạng các chuỗi, nhưng một số thuật toán hoàn toàn có thể áp dụng cho các loại palindrome khác trong Java. Tại sao bạn có thể muốn tìm kiếm palindromes? Trên thực tế, chúng ta không thường xuyên phải tìm kiếm palindromes trong cuộc sống hàng ngày. Đó là một loại nhiệm vụ rất cụ thể. Nếu chúng ta nhớ lại các thuật toán chuỗi, thường xuyên hơn trong thực tế, các lập trình viên có thể thấy việc tìm kiếm một chuỗi con trong một chuỗi chứ không phải tìm kiếm các palindromes hoặc số của chúng. Tuy nhiên, các bài toán liên quan đến palindrome có những ứng dụng quan trọng. Đầu tiên là lập trình olympiad. Có thể có các nhiệm vụ để xác định palindromes. Ứng dụng thứ hai phù hợp với các lập trình viên mới làm quen là phỏng vấn. Tại một cuộc phỏng vấn kỹ thuật, bạn có thể được yêu cầu viết nhanh một chương trình để kiểm tra xem một chuỗi có phải là đối xứng hay không, thậm chí có thể trên một tờ giấy. Chà, trong khoa học, ứng dụng thiết thực nhất để tìm ra các palindrome là các thuật toán sinh học. Theo Wikipedia, tính đối xứng của các hợp chất sinh học đóng một vai trò quan trọng trong tính chất của các hợp chất sinh học khác nhau.

Ví dụ mã thuật toán Palindrome

Nghĩ thử xem. Một chuỗi là một dãy ký tự, người ta có thể nói, một mảng char. Sẽ hợp lý nhất nếu theo trình tự này từ hai bên đến giữa và so sánh các ký tự cực đoan. Nếu cho đến khi chúng ta đạt đến giữa, tất cả các ký tự của chúng ta khớp với nhau, thì chúng ta có một bảng màu nhạt. Hãy tạo một phương thức boolean validPalindrome(String s) để kiểm tra xem String có phải là palindrome không. Mã Java ở đây:

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


   }

}

Trong phương pháp chính, chúng tôi kiểm tra các chuỗi palindromic “cấp độ”, “mát mẻ”, “Bà” và "Bây giờ, thưa ông, một cuộc chiến đã thắng!". Như bạn có thể thấy, cái thứ nhất, thứ ba và thứ tư là palindromes, nhưng cái thứ hai thì không. Chương trình sẽ cung cấp những gì? Vì vậy, cái đầu tiên là một bảng màu, cái thứ hai thì không. Tuy nhiên, có gì sai với thứ ba và thứ tư? Tại sao kết quả là sai ? Có thể bạn đã đoán được vấn đề là một số ký tự trong chuỗi này là chữ hoa và một số là chữ thường, và đối với Java M và m là hai ký tự khác nhau. Hãy cải thiện chương trình để tính đến sự khác biệt này. Đây là một chương trình để kiểm tra xem một chuỗi có phải là một bảng màu hay không để giải quyết các vấn đề về chữ hoa và chữ thường.

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


   }

}

Lần này kết quả dễ đoán hơn đối với chúng tôi: Chà… không chính xác có thể dự đoán được. Tình hình với “Bà” đang trở nên tốt hơn, nhưng điều gì sẽ xảy ra với câu chuyện dài và vui vẻ của chúng ta “Bây giờ, thưa ông, một cuộc chiến đã thắng!”. Điều này khá dễ dàng, nếu bạn nhớ rằng tất cả các dấu cách và ký hiệu dấu chấm câu đều giống như các chữ cái đối với Java. Vì vậy, chúng tôi cần cải thiện thuật toán của mình một lần nữa để sửa lỗi sơ suất này. Hãy dạy chương trình của chúng ta bỏ qua dấu cách và dấu chấm câu. Nói một cách đơn giản, chúng tôi bỏ qua tất cả các ký tự không phải chữ và số. Đây là chương trình palindrome cải tiến trong 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);


   }

}

Ít nhất kết quả là những gì chúng tôi mong đợi từ nó: Có lẽ, nếu bạn mới bắt đầu lập trình, bạn sẽ khó hiểu cách thức hoạt động của các thuật toán so sánh và duyệt chuỗi. Tất nhiên, tốt hơn là bạn nên giải quyết vấn đề này, nhưng bạn có thể viết một phiên bản đơn giản hóa của chính đoạn văn thông qua mảng ký tự, mà thực tế là một chuỗi. Bạn có thể sử dụng phương thức StringBuffer.reverse để kiểm tra xem một chuỗi có phải là một palindrome hay không. Hãy thực hiện phiên bản đơn giản nhất mà không cần kiểm tra các ký hiệu không phải chữ và số cũng như chữ hoa và chữ thường.

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


   }
}

Kết quả giống như trong ví dụ đầu tiên Nếu muốn, bạn có thể cải thiện chương trình này như chúng tôi đã làm với ví dụ đầu tiên. Để củng cố những gì bạn đã học, chúng tôi khuyên bạn nên xem một video bài học từ Khóa học Java của chúng tôi