数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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
更新于: 27-Feb-2021
211 次浏览
广告