Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/valid-palindrome/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Một câu được gọi là đối xứng khi mà bạn bỏ hết tất cả kí tự đặc biệt không phải chữ và số, đọc xuôi hay ngược thì chúng đều như nhau.
Cho một chuỗi s, kiểm tra và trả về true nếu s là chuỗi đối xứng, false nếu không phải.
Điều kiện:
1 <= s.length <= 2 * 10^5.schỉ bao gồm các kí tự ASCII in được.
Bài toán minh họa 1:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Bài toán minh họa 2:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Bài toán minh họa 3:
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
3. Phân tích
Ấu kề! Bài này cũng không có gì quá phức tạp. Điều đầu tiên tôi nghĩ tới khi làm bài này ấy là sử dụng class StringBuilder với đối tượng tên sb, bởi trong class này có sẵn method reverse() đảo ngược tất cả kí tự trong chuỗi.
Nếu các bạn quan tâm có thể đọc thêm bài viết của tôi về StringBuilder tại đây.
Ngay từ ví dụ minh họa 1, ta có thể thấy trong chuỗi s có khả năng sẽ xuất hiện kí tự đặc biệt không phải chữ hoặc số, điển hình như là dấu phẩy ,, dấu hai chấm :, dấu chấm phẩy ;, khoảng trắng giữa các từ , v.v… Vậy thì chúng ta sẽ sử dụng một method có sẵn trong class String để loại bỏ hết tất cả các kí tự này, đó chính là replaceAll(). Tuy nhiên, chúng ta không thể ngồi liệt kê hết tất cả kí tự đặc biệt được, như thế rất mất thời gian và dài dòng.
Rất may là chúng ta có partten "[^a-zA-Z0-9]", đoạn này nghĩa là các ký tự không thuộc các khoảng: a-z, A-Z, hoặc 0-9. Ta thay đoạn này bằng "", như vậy chúng ta sẽ loại bỏ được hết những kí tự đặc biệt không phải chữ hoặc số, s lúc này sẽ bao gồm một chuỗi các kí tự viết liền nhau.
Sau đó ta sẽ gán hết tất cả kí tự của s lúc này vào sb để sau đó sử dụng method reverse().
Cuối cùng ta chỉ việc so sánh xem là sb có giống với s không? Nếu có thì trả về true, không thì trả về false.
4. Code chạy bằng cơm
Đầu tiên thì chúng ta cần một đối tượng StringBuilder tên sb để lát nữa còn đảo ngược:
Tiếp đó, ta cần bỏ hết tất cả kí tự đặc biệt không phải chữ hoặc số, kể cả khoảng trắng với method replaceAll():
Sau đó ta chuyển hết tất cả chữ cái trong s về dạng chữ thường với method toLowerCase():
Giờ thì ta thêm toàn bộ kí tự trong s vào sb bằng vòng lặp for và method append():
Sau khi thêm xong thì ta đảo ngược sb thôi:
Đảo xong thì so sánh xem sb có giống với s không? Nếu giống thì trả về true, không thì false:
Done! Chúng ta tới bước tiếp theo thôi!!!
5. Code thôi chờ gì nữa
Code của chúng ta sẽ như sau:
public static boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
for (char c : s.toCharArray()) {
sb.append(c);
}
sb.reverse();
if (sb.toString().equals(s)) {
return true;
}
return false;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận