Dãy Palindrome:
Một dãy chuỗi được gọi là palindrome nếu đọc từ trước ra sau và từ sau ra trước đều giống nhau. Ví dụ: 'aba', 'madam', 'did' đều là dãy palindrome hợp lệ.
Chúng ta cần viết một hàm JavaScript nhận vào một chuỗi làm đối số duy nhất. Chuỗi đầu vào chỉ chứa các ký tự 'a', 'b', 'c', 'd'. Hàm phải đếm và trả về số lượng tất cả các dãy con palindrome (liên tục hoặc không liên tục) xuất hiện trong chuỗi.
Ví dụ:
Nếu chuỗi đầu vào là:
const str = 'bccb';
Kết quả đầu ra nên là:
const output = 6;
vì các chuỗi palindrome ở đây là: 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'
Ví dụ
Mã thực hiện:
const str = 'bccb'; const countPalindromes = (str = '') => { let base = 1000000007; const dp = Array(str.length).fill([]); for (let l = 1; l <= str.length; l ++) { for (let i = 0; i + l - 1 < str.length; i ++) { let j = i + l - 1; if (l === 1) { dp[i][j] = 1; continue; } if (l === 2) { dp[i][j] = 2; continue; } if (str[i] === str[j]) { let left = i + 1, right = j - 1; while (left <= right && str[left] != str[i]) { left ++; } while (left <= right && str[right] != str[i]) { right --; } if (left > right) { dp[i][j] = dp[i + 1][j - 1] * 2 + 2; } else if (left === right) { dp[i][j] = dp[i + 1][j - 1] * 2 + 1; } else { dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1]; } } else { dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]; } dp[i][j] = dp[i][j] < 0? dp[i][j] + base : dp[i][j] % base; } } return dp[0][str.length - 1]; }; console.log(countPalindromes(str));
Kết quả
Kết quả in ra console:
6