Java | LeetCode
Задача: 730. Count Different Palindromic Subsequences
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.
Пример:
Input: s = "bccb"
Output: 6
👨💻 Алгоритм:
1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.
2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.
3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.
😎 Решение:
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];
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 685 ·