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中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
C语言线程池的常见实现方式详解

C语言线程池的常见实现方式详解

《C语言线程池的常见实现方式详解》本文介绍了如何使用C语言实现一个基本的线程池,线程池的实现包括工作线程、任务队列、任务调度、线程池的初始化、任务添加、销毁等步骤,感兴趣的朋友跟随小编一起看看吧... 目录1. 线程池的基本结构2. 线程池的实现步骤3. 线程池的核心数据结构4. 线程池的详细实现4.1 初
阅读更多...
C#中字符串分割的多种方式

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用
阅读更多...
opencv实现像素统计的示例代码

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量
阅读更多...
如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

《如何使用Bash脚本中的time命令来统计命令执行时间(中英双语)》本文介绍了如何在Bash脚本中使用`time`命令来测量命令执行时间,包括`real`、`user`和`sys`三个时间指标,... 使用 Bash 脚本中的 time 命令来统计命令执行时间在日常的开发和运维过程中，性能监控和优化是不
阅读更多...
Java中JSON字符串反序列化(动态泛型)

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求：定时任务扫描，反射调用目标对象，但是，方法的传参不是固定的。方案一：将方法参数存成jsON字
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
2. c#从不同cs的文件调用函数

2. c#从不同cs的文件调用函数

1.文件目录如下： 2. Program.cs文件的主函数如下 using System;using System.Collections.Generic;using System.Linq;using System.Threading.Tasks;using System.Windows.Forms;namespace datasAnalysis{internal static
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2