730. Count Different Palindromic Subsequences
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.
Пример:
Input: s = "bccb"
Output: 6
C# решение
сопоставлено/оригиналpublic class Solution {
public int CountPalindromicSubsequences(string s) {
const int MOD = 1000000007;
int n = s.Length;
int[,] dp = new int[n, n];
for (int i = 0; i < n; i++) {
dp[i, i] = 1;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (s[i] == s[j]) {
int l = i + 1, r = j - 1;
while (l <= r && s[l] != s[i]) l++;
while (l <= r && s[r] != s[j]) r--;
if (l > r) {
dp[i, j] = dp[i + 1, j - 1] * 2 + 2;
} else if (l == r) {
dp[i, j] = dp[i + 1, j - 1] * 2 + 1;
} else {
dp[i, j] = dp[i + 1, j - 1] * 2 - dp[l + 1, r - 1];
}
} else {
dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
}
dp[i, j] = (dp[i, j] + MOD) % MOD;
}
}
return dp[0, n - 1];
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int CountPalindromicSubsequences(string s) {
const int MOD = 1000000007;
int n = s.size();
int[,] dp = new int[n, n];
for (int i = 0; i < n; i++) {
dp[i, i] = 1;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (s[i] == s[j]) {
int l = i + 1, r = j - 1;
while (l <= r && s[l] != s[i]) l++;
while (l <= r && s[r] != s[j]) r--;
if (l > r) {
dp[i, j] = dp[i + 1, j - 1] * 2 + 2;
} else if (l == r) {
dp[i, j] = dp[i + 1, j - 1] * 2 + 1;
} else {
dp[i, j] = dp[i + 1, j - 1] * 2 - dp[l + 1, r - 1];
}
} else {
dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
}
dp[i, j] = (dp[i, j] + MOD) % MOD;
}
}
return dp[0, n - 1];
}
}Java решение
сопоставлено/оригиналpublic class Solution {
public int countPalindromicSubsequences(String s) {
int MOD = 1000000007;
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (s.charAt(i) == s.charAt(j)) {
int l = i + 1, r = j - 1;
while (l <= r && s.charAt(l) != s.charAt(i)) l++;
while (l <= r && s.charAt(r) != s.charAt(j)) r--;
if (l > r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (l == r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] + MOD) % MOD;
}
}
return dp[0][n - 1];
}
}JavaScript решение
сопоставлено/оригиналvar countPalindromicSubsequences = function(s) {
const MOD = 10**9 + 7;
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (let length = 2; length <= n; length++) {
for (let i = 0; i <= n - length; i++) {
const j = i + length - 1;
if (s[i] === s[j]) {
let l = i + 1, r = j - 1;
while (l <= r && s[l] !== s[i]) l++;
while (l <= r && s[r] !== s[j]) r--;
if (l > r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (l === r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] + MOD) % MOD;
}
}
return dp[0][n - 1];
};Python решение
сопоставлено/оригиналdef countPalindromicSubsequences(s):
MOD = 10**9 + 7
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
l, r = i + 1, j - 1
while l <= r and s[l] != s[i]:
l += 1
while l <= r and s[r] != s[j]:
r -= 1
if l > r:
dp[i][j] = dp[i + 1][j - 1] * 2 + 2
elif l == r:
dp[i][j] = dp[i + 1][j - 1] * 2 + 1
else:
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]
else:
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
dp[i][j] = (dp[i][j] + MOD) % MOD
return dp[0][n - 1]Go решение
сопоставлено/оригиналpackage main
func countPalindromicSubsequences(s string) int {
const MOD = 1000000007
n := len(s)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for i := 0; i < n; i++ {
dp[i][i] = 1
}
for length := 2; length <= n; length++ {
for i := 0; i <= n-length; i++ {
j := i + length - 1
if s[i] == s[j] {
l, r := i+1, j-1
for l <= r && s[l] != s[i] {
l++
}
for l <= r && s[r] != s[j] {
r--
}
if l > r {
dp[i][j] = dp[i+1][j-1]*2 + 2
} else if l == r {
dp[i][j] = dp[i+1][j-1]*2 + 1
} else {
dp[i][j] = dp[i+1][j-1]*2 - dp[l+1][r-1]
}
} else {
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
}
dp[i][j] = (dp[i][j] + MOD) % MOD
}
}
return dp[0][n-1]
}Algorithm
Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.
Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.
Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.