125. Valid Palindrome

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/group-anagrams/description/

Table of Contents

1. Cách tiếp cận vấn đề

Một cụm từ là palindrome nếu sau khi chuyển đổi tất cả các chữ cái viết hoa thành chữ cái viết thường và xóa tất cả các ký tự không phải chữ số và chữ cái, mà dạng viết ngược và viết xuôi của nó là giống nhau.

Và nhiệm vụ của chúng ta ở bài này là từ 1 input chuỗi string cho trước, nếu chuỗi đó là padindrome thì trả về true, ngược lại trả về false.

Viết xuôi và ngược giống nhau? Điều này dễ khiến chúng ta có một cách làm đó là clone string input ra một string khác rồi dùng API có sẵn của ngôn ngữ hoặc tự viết utils để đảo ngược lại cloned string đó, rồi sau đó compare 2 string lại với nhau. Tuy nhiên cách làm này bắt buộc ta phải sử dụng thêm 1 string nữa, và cũng cần phải chuẩn hóa lại string trước khi so sánh (loại bỏ các ký tự không phải là chữ cái và số, biến tất cả ký tự viết hoa thành viết thường).

Đó chính là lý do mà kỹ thuật 2 pointers ra đời để giải quyết những bài toán như thế này. Ta chỉ cần thao tác trực tiếp trên input string ban đầu mà vẫn giữ độ phức tạp về mặt thời gian là O(n).

2. Solution & Phân Tích

Ta sẽ sử dụng kỹ thuật 2 pointers, với 2 con trỏ lần lượt nằm ở đầu với index 0 và cuối chuỗi input với index n - 1 (n là số lượng ký tự trong chuỗi input).
  • Với con trỏ trái left, ta sẽ di chuyển nó từ đầu chuỗi đến cuối chuỗi cho đến khi gặp một ký tự là chữ cái hoặc số. Hay nói cách khác ta tăng giá trị cho left. từ 0 đến n - 1.
  • Tương tự với con trỏ phải right, ta sẽ di chuyển nó từ cuối chuỗi đến đầu chuỗi cho đến khi gặp một ký tự là chữ hoặc số. Hay nói cách khác ta giảm giá trị cho right từ n - 1 đến 0.
  • Nếu lúc này vị trí của hai con trỏ là hợp lệ: vị trí của con trỏ trái phải nhỏ hơn con trỏ phải
    • Ta sẽ tiến hành so sánh giá trị mà hai con trỏ này đang nắm giữ, nếu chúng khác nhau, ta có thể kết luận chuỗi này không phải là Palindrome và return về false ngay lập tức.
    • Nếu giá trị của chúng là bằng nhau, ta sẽ tiếp tục tăng con trỏ left, và giảm con trỏ right để tìm kiếm tiếp các cặp giá trị và so sánh tiếp.
  • Nếu sau khi duyệt qua tất cả các cặp mà không tìm thấy các giá trị khác nhau, ta có thể kết luận chuỗi input là palindrome và trả về true.
Time-Complexity: O(n)
Space-Complexity: O(1)
Với n là số lượng các ký tự của chuỗi input.

3. Code

Trong Java, class Character có hỗ trợ hàm kiểm tra ký tự là chữ cái hoặc chữ số: isLetterOrDigit(char c), và hàm để hỗ trợ chuyển ký tự về in thường: toLowerCase(char c). Các bạn hoàn toàn có thể tự viết hàm riêng để kiểm tra hoặc sử dụng các phương thức được hỗ trợ khác trong ngôn ngữ lập trình mà các bạn hay dùng.