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反转字符串的五种方法总结

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》：本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一：使用StringBuilder的reverse()方法方法二：使用字符数组方法三：使用自
阅读更多...
C语言中的浮点数存储详解

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》：本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来，讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问：十进制小数0.5该如何存储？2.3 浮点
阅读更多...
Golang中拼接字符串的6种方式性能对比

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的，对于拼接字
阅读更多...
基于Python实现多语言朗读与单词选择测验

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、
阅读更多...
C++实现回文串判断的两种高效方法

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法：解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一：将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、
阅读更多...
Java对象和JSON字符串之间的转换方法(全网最清晰)

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》：本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
使用Go语言开发一个命令行文件管理工具

使用Go语言开发一个命令行文件管理工具

《使用Go语言开发一个命令行文件管理工具》这篇文章主要为大家详细介绍了如何使用Go语言开发一款命令行文件管理工具,支持批量重命名,删除,创建,移动文件,需要的小伙伴可以了解下... 目录一、工具功能一览二、核心代码解析1. 主程序结构2. 批量重命名3. 批量删除4. 创建文件/目录5. 批量移动三、如何安
阅读更多...
Java中String字符串使用避坑指南

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下：1. 字符串的不可变性：每次修改都创建新对象2. 使用 == 比较字符串，陷阱满
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2