Bài viết này dựa trên Free Code Camp Basic Algorithm Scripting “Check for Palindromes”.
một bảng màu là một từ, cụm từ, số hoặc chuỗi ký tự khác đọc ngược hoặc xuôi giống nhau. Từ “palindrome” lần đầu tiên được đặt ra bởi nhà viết kịch người Anh Ben Jonson vào thế kỷ 17, từ nguồn gốc Hy Lạp palin (“một lần nữa”) và người máy bay (“đường, hướng”). — src. Wikipedia
Trong bài viết này, tôi sẽ giải thích hai cách tiếp cận, cách thứ nhất là sử dụng các hàm dựng sẵn và cách thứ hai là sử dụng vòng lặp for.
Thử thách thuật toán
Trả về true nếu chuỗi đã cho là một palindrome. Nếu không, trả về sai.
Palindrome là một từ hoặc câu được đánh vần theo cùng một cách cả về phía trước và phía sau, bỏ qua dấu câu, trường hợp và khoảng cách.
Ghi chú. Bạn sẽ cần phải loại bỏ tất cả các ký tự không phải chữ và số (dấu chấm câu, dấu cách và ký hiệu) và biến mọi thứ thành chữ thường để kiểm tra đối xứng.
Chúng tôi sẽ chuyển các chuỗi có định dạng khác nhau, chẳng hạn như “xe đua”, “Xe đua” và “Xe đua” trong số những chuỗi khác.
function palindrome(str) {
return true;
}
palindrome("eye");
Các trường hợp thử nghiệm được cung cấp
- palindrome (“xe đua”) nên trả về đúng
- palindrome(“không phải là palindrome”) nên trả về sai
- palindrome(“Một người đàn ông, một kế hoạch, một con kênh. Panama”) nên trả về đúng
- palindrome(“không bao giờ lẻ hoặc chẵn”) nên trả về đúng
- đối xứng (“không”) nên trả về sai
- palindrome(“gần như”) nên trả về sai
- palindrome(“Tuổi của tôi là 0, 0 si ega ym.”) nên trả về đúng
- palindrome(“1 mắt đổi 1 mắt.”) nên trả về sai
- bảng màu(“0_0 (: /-\:) 0–0”) nên trả về đúng
Cái mà Biểu hiện thông thường chúng ta có cần vượt qua trường hợp thử nghiệm cuối cùng không?
Biểu thức chính quy là các mẫu được sử dụng để so khớp các tổ hợp ký tự trong chuỗi.
Khi tìm kiếm đối sánh yêu cầu nhiều thứ hơn là đối sánh trực tiếp, mẫu bao gồm các ký tự đặc biệt.
To pass the last test case, we can use two Regular Expressions:
/[^A-Za-z0–9]/g or
/[\W_]/g
\W loại bỏ tất cả các ký tự không phải chữ và số:
- \W khớp với bất kỳ ký tự không phải từ nào
- \W tương đương với [^A-Za-z0–9_]
- \W khớp với bất kỳ thứ gì không được đặt trong ngoặc
Điều đó nghĩa là gì?
[^A-Z] matches anything that is not enclosed between A and Z
[^a-z] matches anything that is not enclosed between a and z
[^0-9] matches anything that is not enclosed between 0 and 9
[^_] matches anything that does not enclose _
Nhưng trong trường hợp thử nghiệm của chúng tôi, chúng tôi cần palindrome(“0_0 (: /-\ 🙂 0–0“) trở về thậtnghĩa là “_(: /-\:)–” phải phù hợp.
Chúng tôi sẽ cần thêm “_” để vượt qua trường hợp thử nghiệm cụ thể này.
We now have “\W_”
Chúng tôi cũng sẽ cần phải thêm các g cờ cho tìm kiếm toàn cầu.
We finally have “/[\W_]/g”
/[\W_]/g đã được sử dụng cho mục đích minh họa thuần túy để cho thấy cách thức hoạt động của RegExp. /[^A-Za-z0–9]/g là RegExp dễ chọn nhất.
1. Kiểm tra Palindromes với chức năng tích hợp
Đối với giải pháp này, chúng tôi sẽ sử dụng một số phương pháp:
- Các toLowerCase() phương thức trả về giá trị chuỗi gọi được chuyển đổi thành chữ thường.
- Các thay thế() phương thức trả về một chuỗi mới với một số hoặc tất cả các kết quả khớp của một mẫu được thay thế bằng một chuỗi thay thế. Chúng tôi sẽ sử dụng một trong những RegExp mà chúng tôi vừa tạo trước đó.
- Các tách ra() phương thức tách một đối tượng Chuỗi thành một mảng các chuỗi bằng cách tách chuỗi thành các chuỗi con.
- Các đảo ngược() phương pháp đảo ngược một mảng tại chỗ. Phần tử mảng đầu tiên trở thành phần tử cuối cùng và phần tử cuối cùng trở thành phần tử đầu tiên.
- Các tham gia() phương thức nối tất cả các phần tử của một mảng thành một chuỗi.
function palindrome(str) {
// Step 1. Lowercase the string and use the RegExp to remove unwanted characters from it
var re = /[\W_]/g; // or var re = /[^A-Za-z0-9]/g;
var lowRegStr = str.toLowerCase().replace(re, '');
// str.toLowerCase() = "A man, a plan, a canal. Panama".toLowerCase() = "a man, a plan, a canal. panama"
// str.replace(/[\W_]/g, '') = "a man, a plan, a canal. panama".replace(/[\W_]/g, '') = "amanaplanacanalpanama"
// var lowRegStr = "amanaplanacanalpanama";
// Step 2. Use the same chaining methods with built-in functions from the previous article 'Three Ways to Reverse a String in JavaScript'
var reverseStr = lowRegStr.split('').reverse().join('');
// lowRegStr.split('') = "amanaplanacanalpanama".split('') = ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"]
// ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"].reverse() = ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"]
// ["a", "m", "a", "n", "a", "p", "l", "a", "n", "a", "c", "a", "n", "a", "l", "p", "a", "n", "a", "m", "a"].join('') = "amanaplanacanalpanama"
// So, "amanaplanacanalpanama".split('').reverse().join('') = "amanaplanacanalpanama";
// And, var reverseStr = "amanaplanacanalpanama";
// Step 3. Check if reverseStr is strictly equals to lowRegStr and return a Boolean
return reverseStr === lowRegStr; // "amanaplanacanalpanama" === "amanaplanacanalpanama"? => true
}
palindrome("A man, a plan, a canal. Panama");
function palindrome(str) {
var re = /[\W_]/g;
var lowRegStr = str.toLowerCase().replace(re, '');
var reverseStr = lowRegStr.split('').reverse().join('');
return reverseStr === lowRegStr;
}
palindrome("A man, a plan, a canal. Panama");
2. Kiểm tra Palindromes Với vòng lặp FOR
Lập chỉ mục một nửa (len/2) có lợi ích khi xử lý các chuỗi lớn. Chúng tôi kiểm tra phần cuối của mỗi phần và chia số lần lặp bên trong vòng lặp FOR cho hai.
function palindrome(str) {
// Step 1. The first part is the same as earlier
var re = /[^A-Za-z0-9]/g; // or var re = /[\W_]/g;
str = str.toLowerCase().replace(re, '');
// Step 2. Create the FOR loop
var len = str.length; // var len = "A man, a plan, a canal. Panama".length = 30
for (var i = 0; i < len/2; i++) {
if (str[i] !== str[len - 1 - i]) { // As long as the characters from each part match, the FOR loop will go on
return false; // When the characters don't match anymore, false is returned and we exit the FOR loop
}
/* Here len/2 = 15
For each iteration: i = ? i < len/2 i++ if(str[i] !== str[len - 1 - i])?
1st iteration: 0 yes 1 if(str[0] !== str[15 - 1 - 0])? => if("a" !== "a")? // false
2nd iteration: 1 yes 2 if(str[1] !== str[15 - 1 - 1])? => if("m" !== "m")? // false
3rd iteration: 2 yes 3 if(str[2] !== str[15 - 1 - 2])? => if("a" !== "a")? // false
4th iteration: 3 yes 4 if(str[3] !== str[15 - 1 - 3])? => if("n" !== "n")? // false
5th iteration: 4 yes 5 if(str[4] !== str[15 - 1 - 4])? => if("a" !== "a")? // false
6th iteration: 5 yes 6 if(str[5] !== str[15 - 1 - 5])? => if("p" !== "p")? // false
7th iteration: 6 yes 7 if(str[6] !== str[15 - 1 - 6])? => if("l" !== "l")? // false
8th iteration: 7 yes 8 if(str[7] !== str[15 - 1 - 7])? => if("a" !== "a")? // false
9th iteration: 8 yes 9 if(str[8] !== str[15 - 1 - 8])? => if("n" !== "n")? // false
10th iteration: 9 yes 10 if(str[9] !== str[15 - 1 - 9])? => if("a" !== "a")? // false
11th iteration: 10 yes 11 if(str[10] !== str[15 - 1 - 10])? => if("c" !== "c")? // false
12th iteration: 11 yes 12 if(str[11] !== str[15 - 1 - 11])? => if("a" !== "a")? // false
13th iteration: 12 yes 13 if(str[12] !== str[15 - 1 - 12])? => if("n" !== "n")? // false
14th iteration: 13 yes 14 if(str[13] !== str[15 - 1 - 13])? => if("a" !== "a")? // false
15th iteration: 14 yes 15 if(str[14] !== str[15 - 1 - 14])? => if("l" !== "l")? // false
16th iteration: 15 no
End of the FOR Loop*/
}
return true; // Both parts are strictly equal, it returns true => The string is a palindrome
}
palindrome("A man, a plan, a canal. Panama");
function palindrome(str) {
var re = /[^A-Za-z0-9]/g;
str = str.toLowerCase().replace(re, '');
var len = str.length;
for (var i = 0; i < len/2; i++) {
if (str[i] !== str[len - 1 - i]) {
return false;
}
}
return true;
}
palindrome("A man, a plan, a canal. Panama");
Tôi hy vọng bạn tìm thấy điều này hữu ích. Đây là một phần trong loạt bài viết “Cách giải quyết các thuật toán FCC” của tôi về Các thách thức về thuật toán của Free Code Camp, trong đó tôi đề xuất một số giải pháp và giải thích từng bước những gì xảy ra bên trong.
Hai cách để xác nhận kết thúc của Chuỗi trong JavaScript
Trong bài viết này, tôi sẽ giải thích cách giải quyết thử thách “Xác nhận Kết thúc” của freeCodeCamp.
Ba cách để đảo ngược một chuỗi trong JavaScript
Bài viết này dựa trên Free Code Camp Basic Algorithm Scripting “Reverse a String”
Ba cách để thừa số hóa một số trong JavaScript
Bài viết này dựa trên Free Code Camp Basic Algorithm Scripting “Factorialize a Number”
Ba cách để tìm từ dài nhất trong chuỗi trong JavaScript
Bài viết này dựa trên Kịch bản thuật toán cơ bản của Free Code Camp “Tìm từ dài nhất trong một chuỗi”.
Ba cách đặt tiêu đề cho một câu trong JavaScript
Bài viết này dựa trên Kịch bản thuật toán cơ bản của Free Code Camp “Tiêu đề trường hợp một câu”.
Ba cách bạn có thể tìm thấy số lớn nhất trong một mảng bằng JavaScript
Trong bài viết này, tôi sẽ giải thích cách giải quyết thử thách “Trả về số lớn nhất trong mảng” của Free Code Camp. Cái này…
Nếu bạn có giải pháp của riêng mình hoặc bất kỳ đề xuất nào, hãy chia sẻ chúng bên dưới phần bình luận.
Hoặc bạn có thể theo dõi tôi trên Trung bình, TwitterGithub và LinkedInngay sau khi bạn nhấp vào trái tim màu xanh bên dưới 😉
#StayCurious, #KeepOnHacking & #MakeItHappen!