Problem:
Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7
.
A subsequence of a string S is obtained by deleting 0 or more characters from S.
A sequence is palindromic if it is equal to the sequence reversed.
Two sequences A_1, A_2, ...
and B_1, B_2, ...
are different if there is some i
for which A_i != B_i
.
Example 1:
Input: S = 'bccb' Output: 6 Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'. Note that 'bcb' is counted only once, even though it occurs twice.
Example 2:
Input: S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba' Output: 104860361 Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.
Note:
- The length of
S
will be in the range[1, 1000]
. - Each character
S[i]
will be in the set{'a', 'b', 'c', 'd'}
.
Idea:
DP
Solution 1: Recursion with memoization
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// Author: Huahua // Runtime: 72 ms class Solution { public: int countPalindromicSubsequences(const string& S) { const int n = S.length(); m_ = vector<vector<int>>(n + 1, vector<int>(n + 1, 0)); return count(S, 0, S.length() - 1); } private: static constexpr long kMod = 1000000007; long count(const string& S, int s, int e) { if (s > e) return 0; if (s == e) return 1; if (m_[s][e] > 0) return m_[s][e]; long ans = 0; if (S[s] == S[e]) { int l = s + 1; int r = e - 1; while (l <= r && S[l] != S[s]) ++l; while (l <= r && S[r] != S[s]) --r; if (l > r) ans = count(S, s + 1, e - 1) * 2 + 2; else if (l == r) ans = count(S, s + 1, e - 1) * 2 + 1; else ans = count(S, s + 1, e - 1) * 2 - count(S, l + 1, r - 1); } else { ans = count(S, s, e - 1) + count(S, s + 1, e) - count(S, s + 1, e - 1); } return m_[s][e] = (ans + kMod) % kMod; } vector<vector<int>> m_; }; |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
""" Author: Huahua Runtime: 3582 ms """ class Solution: def countPalindromicSubsequences(self, S): def count(S, i, j): if i > j: return 0 if i == j: return 1 if self.m_[i][j]: return self.m_[i][j] if S[i] == S[j]: ans = count(S, i + 1, j - 1) * 2 l = i + 1 r = j - 1 while l <= r and S[l] != S[i]: l += 1 while l <= r and S[r] != S[i]: r -= 1 if l > r: ans += 2 elif l == r: ans += 1 else: ans -= count(S, l + 1, r - 1) else: ans = count(S, i + 1, j) + count(S, i, j - 1) - count(S, i + 1, j - 1) self.m_[i][j] = ans % 1000000007 return self.m_[i][j] n = len(S) self.m_ = [[None for _ in range(n)] for _ in range(n)] return count(S, 0, n - 1) |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Author: Huahua // Runtime: 107 ms class Solution { private int[][] m_; private static final int kMod = 1000000007; public int countPalindromicSubsequences(String S) { int n = S.length(); m_ = new int[n][n]; return count(S.toCharArray(), 0, n - 1); } private int count(char[] s, int i, int j) { if (i > j) return 0; if (i == j) return 1; if (m_[i][j] > 0) return m_[i][j]; long ans = 0; if (s[i] == s[j]) { ans += count(s, i + 1, j - 1) * 2; int l = i + 1; int r = j - 1; while (l <= r && s[l] != s[i]) ++l; while (l <= r && s[r] != s[i]) --r; if (l > r) ans += 2; else if (l == r) ans += 1; else ans -= count(s, l + 1, r - 1); } else { ans = count(s, i, j - 1) + count(s, i + 1, j) - count(s, i + 1, j - 1); } m_[i][j] = (int)((ans + kMod) % kMod); return m_[i][j]; } } |
Solution 2: DP
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Author: Huahua // Runtime: 79 ms class Solution { public: int countPalindromicSubsequences(const string& S) { int n = S.length(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) dp[i][i] = 1; for (int len = 1; len <= n; ++len) { for (int i = 0; i < n - len; ++i) { const int j = i + len; if (S[i] == S[j]) { dp[i][j] = dp[i + 1][j - 1] * 2; int l = i + 1; int r = j - 1; while (l <= r && S[l] != S[i]) ++l; while (l <= r && S[r] != S[i]) --r; if (l == r) dp[i][j] += 1; else if (l > r) dp[i][j] += 2; else dp[i][j] -= dp[l + 1][r - 1]; } else { dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]; } dp[i][j] = (dp[i][j] + kMod) % kMod; } } return dp[0][n - 1]; } private: static constexpr long kMod = 1000000007; }; |
Pyhton
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
""" Author: Huahua Runtime: 3639 ms """ class Solution: def countPalindromicSubsequences(self, S): n = len(S) if n == 0: return 0 dp = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): dp[i][i] = 1 for size in range(2, n + 1): for i in range(n - size + 1): j = i + size - 1 if S[i] == S[j]: dp[i][j] = dp[i + 1][j - 1] * 2 l = i + 1 r = j - 1 while l <= r and S[l] != S[i]: l += 1 while l <= r and S[r] != S[i]: r -= 1 if l > r: dp[i][j] += 2 elif l == r: dp[i][j] += 1 else: dp[i][j] -= 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] %= 1000000007 return dp[0][n - 1] |
Related Problems: