Skip to content

Commit 01ddc4b

Browse files
liuyuboboboliuyubobobo
committed
0730 solved.
1 parent 0f5c703 commit 01ddc4b

File tree

3 files changed

+80
-2
lines changed

3 files changed

+80
-2
lines changed

‎0501-1000/0730-Count-Different-Palindromic-Subsequences/cpp-0730/CMakeLists.txt‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.22)
2+
project(cpp_0730)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_0730 main.cpp)

‎0501-1000/0730-Count-Different-Palindromic-Subsequences/cpp-0730/main.cpp‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/// Source : https://leetcode.com/problems/count-different-palindromic-subsequences/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-09
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <cassert>
8+
9+
using namespace std;
10+
11+
12+
/// DP
13+
/// Time Complexity: O(n^2)
14+
/// Space Complexity: O(n^2)
15+
class Solution {
16+
17+
private:
18+
const long long MOD = 1e9 + 7;
19+
20+
public:
21+
int countPalindromicSubsequences(const string& s) {
22+
23+
int n = s.size();
24+
25+
vector<vector<vector<long long>>> dp(4, vector<vector<long long>>(n, vector<long long>(n, 0)));
26+
for(int i = 0; i < n; i ++) dp[s[i] - 'a'][i][i] = 1;
27+
for(int i = 0; i + 1 < n; i ++){
28+
if(s[i] == s[i + 1]) dp[s[i] - 'a'][i][i + 1] = 2;
29+
else{
30+
dp[s[i] - 'a'][i][i + 1] = dp[s[i + 1] - 'a'][i][i + 1] = 1;
31+
}
32+
}
33+
34+
for(int len = 3; len <= n; len ++){
35+
for(int l = 0; l + len - 1 < n; l ++){
36+
int r = l + len - 1;
37+
38+
for(char border = 0; border < 4; border ++){
39+
if(s[l] == s[r] && s[l] == 'a' + border){
40+
dp[border][l][r] = 2;
41+
for(char c = 0; c < 4; c ++)
42+
dp[border][l][r] += dp[c][l + 1][r - 1];
43+
dp[border][l][r] %= MOD;
44+
}
45+
else{
46+
dp[border][l][r] = dp[border][l][r - 1] + dp[border][l + 1][r] - dp[border][l + 1][r - 1] + MOD;
47+
dp[border][l][r] %= MOD;
48+
}
49+
}
50+
}
51+
}
52+
53+
long long res = 0;
54+
for(int border = 0; border < 4; border ++)
55+
res += dp[border][0][n - 1];
56+
return res % MOD;
57+
}
58+
};
59+
60+
61+
int main() {
62+
63+
cout << Solution().countPalindromicSubsequences("bccb") << '\n';
64+
// 6
65+
66+
cout << Solution().countPalindromicSubsequences("abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba") << '\n';
67+
// 104860361
68+
69+
cout << Solution().countPalindromicSubsequences("baccdabbccbdbbbcdbbcdbacdabaaddcdbcabdbddadbdaaadbbdaabbdaccdabbddaaccdbbcdbcdbbaaababdddbdccbbaddabdbdabddbaccddabaccadacddbbbdacacaaddaccbabcbcbbcbcadccbccddcddccdabdabaddacdcdcbdadabbcddacbbbbacbcadbccacddddacbdcddbddbddbcabcbdacadbdccabddaacadddbadbccdacbaabababcababccddacabadbcaacbadcbacaadabbadabaabdbcabdabaddabdcacbdbacbcdcacdcaaccadabacbadcdabddccaaacdaadacbbcadcbbccaccbbbdcbcaabbbddcdaaddbdbbdacdaabacbacdabbbdbdaaddbddadbabcdabaddbbadcaadcddcaaddcdbbbbddcccaacdbdbcccccddadbacbdbcacabddaabcbbbbcadbbcabbabcbcdccdcaddabbbddbbdadbbbdadbbdaaacbbbbdbbcadcbbcddddcacdcbddcaacbaccacaddcdacbadccaabdabadbbcccabddcbbcdaacddaacccbacccacbddbcdcdaabbbacdcbabaaaaaacdabcddbcbaccabacddaccadaaddddaaaccbccdbdcdcdbdccdcbdbddbcdbcbdaacaccdabdbabcdbdbadcbcbbaabaccbbababdbbddbcacadbaaadbcccadaddbccddbcadaccbaddcdacaabbbbdbcddacbdccddaadabbbaccddbcbacbbbcbbbbcbbccdbaccdddaddaaacdababcdabdacdbaacdadbaabcadcddccabcccadabbdbbadbcadbdbaddaabbbcdbbbddcdbddbabcdccddccbaccbabcdcddddabbabdccbaddccacdddadcaadd") << endl;
70+
71+
return 0;
72+
}

‎readme.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -734,7 +734,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
734734
| 727 | [Minimum Window Subsequence](https://leetcode.com/problems/minimum-window-subsequence/description/) | [solution](https://leetcode.com/problems/minimum-window-subsequence/solution/) | [C++](0501-1000/cpp-Minimum-Window-Subsequence/cpp-0727/) | | |
735735
| 728 | [Self Dividing Numbers](https://leetcode.com/problems/self-dividing-numbers/description/) | [solution](https://leetcode.com/problems/self-dividing-numbers/solution/) | [C++](0501-1000/0728-Self-Dividing-Numbers/cpp-0728/) | | |
736736
| 729 | [My Calendar I](https://leetcode.com/problems/my-calendar-i/description/) | [solution](https://leetcode.com/problems/my-calendar-i/solution/) | [C++](0501-1000/0729-My-Calendar-I/cpp-0729/) | | |
737-
| | | | | | |
737+
| 730 | [Count Different Palindromic Subsequences](https://leetcode.com/problems/count-different-palindromic-subsequences/) | [无] | [C++](0501-1000/0730-Count-Different-Palindromic-Subsequences/cpp-0730/) | | |
738738
| 731 | [My Calendar II](https://leetcode.com/problems/my-calendar-ii/description/) | [solution](https://leetcode.com/problems/my-calendar-ii/solution/) | [C++](0501-1000/0731-My-Calendar-II/cpp-0731/) | | |
739739
| 732 | [My Calendar III](https://leetcode.com/problems/my-calendar-iii/description/) | [solution](https://leetcode.com/problems/my-calendar-iii/solution/) | [C++](0501-1000/0732-My-Calendar-III/cpp-0732/) | | |
740740
| 733 | [Flood Fill](https://leetcode.com/problems/flood-fill/description/) | [solution](https://leetcode.com/problems/flood-fill/solution/) | [C++](0501-1000/0733-Flood-Fill/cpp-0733/) | | |
@@ -2132,7 +2132,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21322132
| 2286 | [Booking Concert Tickets in Groups](https://leetcode.com/problems/booking-concert-tickets-in-groups/) | [无] | [C++](2001-2500/2286-Booking-Concert-Tickets-in-Groups/cpp-2286/) | | |
21332133
| 2287 | [Rearrange Characters to Make Target String](https://leetcode.com/problems/rearrange-characters-to-make-target-string/) | [无] | [C++](2001-2500/2287-Rearrange-Characters-to-Make-Target-String/cpp-2287/) | | |
21342134
| 2288 | [Apply Discount to Prices](https://leetcode.com/problems/apply-discount-to-prices/) | [无] | [C++](2001-2500/2288-Apply-Discount-to-Prices/cpp-2288/) | | |
2135-
| 2289 | [Steps to Make Array Non-decreasing](https://leetcode.com/problems/steps-to-make-array-non-decreasing/) | [无] | [C++](2001-2500/2289-Steps-to-Make-Array-Non-decreasing/cpp-2289/) | | |
2135+
| 2289 | [Steps to Make Array Non-decreasing](https://leetcode.com/problems/steps-to-make-array-non-decreasing/) | [无]<br/>[缺：用 C++ STL list] | [C++](2001-2500/2289-Steps-to-Make-Array-Non-decreasing/cpp-2289/) | | |
21362136
| 2290 | [Minimum Obstacle Removal to Reach Corner](https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/) | [无] | [C++](2001-2500/2290-Minimum-Obstacle-Removal-to-Reach-Corner/cpp-2290/) | | |
21372137
| 2291 | [Maximum Profit From Trading Stocks](https://leetcode.com/problems/maximum-profit-from-trading-stocks/) | [无] | [C++](2001-2500/2291-Maximum-Profit-From-Trading-Stocks/cpp-2291/) | | |
21382138
| 2292 | Database Problem: [Link](https://github.com/liuyubobobo/Play-Leetcode-Database/) | - | - | - | - |

0 commit comments

Comments
 (0)