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!
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ì?
mức độ là một palindrome? đúng
là mát mẻ một palindrome? sai
là Madam một palindrome? sai
là Bây giờ, thưa ngài, một cuộc chiến đã thắng! một bảng màu? SAI
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:
mức độ là một palindrome? đúng
là mát mẻ một palindrome? sai
là Madam một palindrome? đúng
là Bây giờ, thưa ngài, một cuộc chiến đã thắng! một bảng màu? SAI
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ó:
mức độ là một palindrome? đúng
là mát mẻ một palindrome? sai
là Madam một palindrome? đúng
là Bây giờ, thưa ngài, một cuộc chiến đã thắng! một bảng màu? ĐÚNG VẬY
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
mức độ là một palindrome? đúng
là mát mẻ một palindrome? sai
là Madam một palindrome? sai
là Bây giờ, thưa ngài, một cuộc chiến đã thắng! một bảng màu? SAI
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
GO TO FULL VERSION