Hướng dẫn dùng valid-palindrome-iii JavaScript
Giải thuật là một vấn đề cực kỳ đau đầu trong lập trình từ trước tới nay, nhưng không có nghĩa ta sẽ bỏ qua nó :D, trong trường đại học ta học giải thuật chủ yếu bằng ngôn ngữ C, nhưng lần này nhờ FCC :)) ta sẽ đi tìm hiểu một cách có hệ thống về các giải thuật cơ bản trong Javascript. Ở bài này ta sẽ đi tìm hiểu về “Kiểm tra một chuỗi có phải là một Palindrome hay không” bằng việc giải quyết bài toán đi từ giải thuật căn bản nhất cho đến giải thuật tối ưu. Palindrome là gì? Palindrome là một từ hoặc một cụm từ mà khi ta đọc xuôi hoặc đọc ngược thì nó cũng như vậy, ví dụ từ moom, race car Mục đích mà chúng ta giải quyết bài toán này đó là để làm sạch chuỗi được pass qua để xác định xem nó có phải là một Palindrome hay không. Cơ sở lý thuyết để giải quyết bài toán Ta dùng RegEx để làm sạch những ký tự không mong muốn khỏi chuỗi Dùng hàm Sử dụng Cách giải cơ bản nhất Trước tiên ta sử dụng hàm replace và RegEx để thay thế bất kỳ một ký tự nào không phải là từ và ký tự _ bằng một null (nghĩa là nothing hay không có gì ở đó cả) replace(/[\W_]/g, '') Nhắc lại một chút về kiến thức RegEx có liên quan tới bài toán này
Tiếp theo, ta lấy chuỗi vừa được replace ở trên và chuyển tất cả các ký tự in hoa sang in thường, vì chữ A khác chữ a. .toLowerCase() Ta có được một cấu trúc hoàn chỉnh như sau: str.replace(/[\W_]/g, '').toLowerCase(); Bước kế tiếp, ta lấy chuỗi đó cắt ra thành từng phần tử riêng biệt với hàm split(”), nghịch đảo chuỗi vừa cắt với hàm reverse() và sau đó nối những phần tử vừa nghịch đảo bằng hàm join(”) str.replace(/[\W_]/g, '').toLowerCase().split('').reverse().join('') Cuối cùng, ta check lại chuỗi theo chiều forwards và chiều backwards và return kết quả return str.replace(/[\W_]/g, '').toLowerCase() === str.replace(/[\W_]/g, '').toLowerCase().split('').reverse().join(''); Phần Code hoàn thiện
Một cách giải khác Ở cách giải này chúng ta sẽ dùng vòng lặp for để lặp qua một lượt các từ nằm trong chuỗi. Nhưng trước tiên ta sẽ đi xử lý chuỗi được pass qua, sao cho mỗi từ trong chuỗi đều là từ viết thường bằng cách dùng hàm toLowerCase() và sử dụng hàm replace() với tham số truyền vào là RegEx và ” (null) để đảm bảo chuỗi không tồn tại các ký tự đặc biệt và dấu gạch dưới. str = str.toLowerCase().replace(/[\W_]/g, ''); Tiếp theo ta set up một vòng lặp for để lặp qua một lượt các từ trong chuỗi như sau for(var i = 0, len = str.length - 1; i < len/2; i++) Trong đó, ta chú ý đến các điểm sau:
Trong vòng lặp for, ta tiến hành kiểm tra từ trong phần tử thứ [i] của chuỗi str[i] có bằng từ nằm trong phần tử xác định bởi chiều dài của chuỗi trừ cho i str.length – i. if (str[i] !== str[len-i]) { return false; } Ở mỗi vòng lặp, phần tử trong chuỗi được kiểm tra ở cả hai phía của chuỗi và di chuyển dần đến trung tâm của chuỗi cho đến khi ta kiểm tra hết tất cả các từ. Nếu ở mỗi từ của chuỗi mà ta đang kiểm tra không khớp nhau thì return false. Nếu vòng lặp hoàn tất thành công ta sẽ có một palindrome và khi đó ta sẽ return true. Phần code hoàn thiện cho giải pháp này
|