Leetcode 730:统计不同回文子字符串 -- C语言

2024-06-02 15:38
文章标签 leetcode 语言 统计 字符串 回文 不同 730

本文主要是介绍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语言的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1024382。

相关文章

Java中的StringBuilder之如何高效构建字符串

Java中的StringBuilder之如何高效构建字符串

《Java中的StringBuilder之如何高效构建字符串》本文将深入浅出地介绍StringBuilder的使用方法、性能优势以及相关字符串处理技术,结合代码示例帮助读者更好地理解和应用,希望对大家... 目录关键点什么是 StringBuilder？为什么需要 StringBuilder？如何使用 St
阅读更多...
Pandas统计每行数据中的空值的方法示例

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据（NaN值）是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值？为什么要统计空值？准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处
阅读更多...
C语言中位操作的实际应用举例

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》：本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合
阅读更多...
Go语言开发实现查询IP信息的MCP服务器

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服
阅读更多...
Java中字符串转时间与时间转字符串的操作详解

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间（一）使用预定义格式（二）自定义格式二、时间转字符串（一）使用预定义格式（二）自
阅读更多...
C 语言中enum枚举的定义和使用小结

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum（枚举）是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚
阅读更多...
Java使用SLF4J记录不同级别日志的示例详解

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J
阅读更多...
Java字符串操作技巧之语法、示例与应用场景分析

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字
阅读更多...
一文详解如何在Python中从字符串中提取部分内容

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》：本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST（抽象语法树）、字符串操作... 目录前言解决方案方法一：使用正则表达式方法二：使用 Pyparsing方法三：使用 AST方法四：使用字
阅读更多...
Java字符串处理全解析(String、StringBuilder与StringBuffer)

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》：本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析：String、StringBuilder与StringBuffer一、St
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2