資料結構
網路
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 次瀏覽
廣告