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 Array.prototype.split, hàm Array.prototype.join, vòng lặp for … while hoặc dùng hàm map[].

Sử dụng String.prototype.toLowerCase để chuyển các ký tự của chuỗi về dạng chữ thườ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

• / … /g là một global regex.
• [ … ] ký hiệu này sẽ tạo ra một character set.
• \W_ sẽ tìm những ký tự không phải là từ [ngược lại với ký hiệu \w sẽ tìm những ký tự là từ] và những ký tự là dấu gạch dưới.

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters

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:

• len = str.length – 1: nghĩa là ta chỉ duyệt các từ trong chuỗi từ vị trí số 0 đến vị trí n – 1, do chuỗi là một mảng bao gồm các từ.
• i < len/2: Ta cài đặt việc thoát ra khỏi vòng lặp khi i nhỏ hơn chiều dài của chuỗi chia hai để báo cho vòng lặp biết nên dừng ở giữa chuỗi

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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters