在 JavaScript 中计算字符串中所有可能的回文子序列

回文序列：

如果一个字符串序列从正面和背面读取相同，则称为回文序列。例如，“aba”、“madam”、“did”都是有效的回文序列。

我们需要编写一个 JavaScript 函数，它接受一个字符串作为第一个也是唯一的参数。作为输入的字符串保证只包含“a”、“b”、“c”和“d”。我们的函数应该计算并返回出现在字符串中的所有连续或非连续回文子序列的数量。

例如 -

如果输入字符串是 -

const str = 'bccb';

那么输出应该是 -

const output = 6;

因为这里的回文字符串是 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'

示例

此代码将是 -

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

控制台中的输出将是 -

6