Đếm tất cả dãy con palindromic có thể có trong một chuỗi trong JavaScript

Trình tự Palindrome:

Một chuỗi chuỗi được gọi là chuỗi palindrome nếu nó đọc giống nhau từ phía trước và phía sau. Ví dụ:'aba', 'madam,' did 'là tất cả các chuỗi palindrome hợp lệ.

Chúng tôi được yêu cầu viết một hàm JavaScript lấy một chuỗi làm đối số đầu tiên và duy nhất. Chuỗi được lấy làm đầu vào được đảm bảo chỉ bao gồm 'a', 'b', 'c' và 'd'. Hàm của chúng ta sẽ đếm và trả về số lượng của tất cả các chuỗi con palindrome liền kề hoặc không liền kề xuất hiện trong chuỗi.

Ví dụ -

Nếu chuỗi đầu vào là -

const str = 'bccb';

Sau đó, đầu ra phải là -

const output = 6;

bởi vì các chuỗi palindrome ở đây là 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'

Ví dụ

Mã cho điều này sẽ là -

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));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

6