本文主要是介绍Leetcode 730:统计不同回文子字符串 -- C语言，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
需求
给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子字符序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：
共有 3104860382 个不同的非空回文子字符序列，对 10^9 + 7 取模为 104860361。
提示：
字符串 S 的长度将在[1, 1000]范围内。
每个字符 S[i] 将会是集合 {'a', 'b', 'c', 'd'} 中的某一个。
思路
使用动态规划方法进行规划，我承认这个算法太TM复杂了，参考了老外的算法进行书写
- 如果 S[i] == S[j]，这时我们需要判断[i, j]这一段中有多少字符与S[i]不相等
- 如果中间没有和S[i]相同的字母，例如"aba"这种情况，dp[i][j] = dp[i + 1][j - 1] * 2 + 2; （dp[i][j] = dp[i + 1][j - 1] * 2 代表的dp[i + 1[j - 1]这一段可以独立存在，也可在外层包裹S[i],S[j]，所有需要x2，而2是代表“aa”和“a”）
- 如果中间只有一个和S[i]相同的字母，就是"aaa"这种情况，dp[i][j] = dp[i + 1][j - 1] * 2 + 1; （x2与上面情况相同，加一单独计算"aa",而“a”在dp[i + 1][j - 1] 中计算过了）
- 否则中间至少有两个和S[i]相同的字母，就是"aabaa"这种情况，dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];（left、right请见代码注释，dp[left + 1][right - 1]这一段重复计算了）
- 否则dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
代码实现
/*
* 需求
给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
通过从 S 中删除 0 个或多个字符来获得子字符序列。
如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
示例 1：
输入：
S = 'bccb'
输出：6
解释：
6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：
共有 3104860382 个不同的非空回文子字符序列，对 10^9 + 7 取模为 104860361。
提示：
字符串 S 的长度将在[1, 1000]范围内。
每个字符 S[i] 将会是集合 {'a', 'b', 'c', 'd'} 中的某一个。
gcc countPalindromicSubsequences.c -g -o a.exe -DDEBUG
*/
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#ifdef DEBUG
#define LOG(fmt, args...) fprintf(stdout, fmt, ##args)
#define BREAKER(a, b, c) breaker(a, b, c)
#else
#define LOG(fmt,...)
#define BREAKER(a, b, c)
#endif
#define TRUE 1
#define FALSE 0
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
int countPalindromicSubsequences(char * S){
if(NULL == S){
return 0;
}
int ** dp = NULL;
int i = 0, j = 0;
int size = strlen(S);
int left = 0, right = 0;
int ret = 0;
int M = 1e9 + 7;
dp = (int ** )malloc(size * (sizeof(int *)));
for(i = 0; i < size; i++){
dp[i] = (int *)malloc(size * sizeof(int));
}
/*数组初始化都是0，这步骤很重要，因为dp算法，后面的计算要依赖前面的值和初始值*/
for(i = 0; i < size; i++){
for(j = 0; j < size; j++){
dp[i][j] = 0;
}
}
for(i = 0; i < size; i++){
dp[i][i] = 1;
}
for(i = size - 2; i >= 0; i--){
for(j = i + 1; j < size; j++){
if(S[i] == S[j]) {
left = i + 1;
right = j - 1;
while(left <= right && S[left] != S[i]){
left++;
}
while(left <= right && S[right] != S[i]){
right--;
}
if(left > right) { /*不包含s[i]*/
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (left == right){ /*包含1个s[i]*/
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else { /*包含2个以上s[i]*/
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] + M : dp[i][j] % M;
}
}
ret = dp[0][size - 1];
free(dp);
dp = NULL;
return ret;
}
void testcountPalindromicSubsequences(void){
printf("\n************ testcountPalindromicSubsequences ************ \n");
int ret = 0;
#if 1
char * str1 = "bccb";
ret = countPalindromicSubsequences(str1);
printf("The Palindromic Subsequences of str %s is %d\n", str1, ret);
char * str2 = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba";
ret = countPalindromicSubsequences(str2);
printf("The Palindromic Subsequences of str %s is %d\n", str2, ret);
#endif
return;
}
int main(int argc, char ** argv){
testcountPalindromicSubsequences();
}
代码编译
gcc countPalindromicSubsequences.c -g -o a.exe -DDEBUG
调试输出
************ testcountPalindromicSubsequences ************ The Palindromic Subsequences of str bccb is 6 The Palindromic Subsequences of str abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba is 104860361
这篇关于Leetcode 730:统计不同回文子字符串 -- C语言的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
