leetcode647回文子串刷题打卡

简介: leetcode647回文子串刷题打卡

647. 回文子串 - 力扣(Leetcode)

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"

示例 2:

输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示:

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成
题解思路:

动归五步:

  • dp数组以及下标含义
  • 布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]true,否则为false
  • 确定递推公式
  • 两种情况
  • s[i] == s[j]
  • 查看ij的距离
  • 如果是<=1则说明是回文(a, aa),dp[i][j] = true
  • 如果>=2则还需要看[i + 1, j - 1]的子序列是不是回文,如果是则dp[i][j] = true
  • s[i] != s[j]
  • 直接按照不是回文处理
  • dp初始化
  • 一开始全部初始化为false,表示还没有开始匹配
  • 遍历顺序 为保证dp[i + 1][j - 1]都是被用到过的 所以遍历要从下到上 从左到右
    由于只会遍历上三角,则j的索引从i开始
for(int i = s.size() - 1; i >= 0; i--)
    for(int j = i; j < s.size(); j++)
完整代码
class Solution {
public:
    int countSubstrings(string s) {
    // dp数组的定义    
        // 布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。
        vector<vector<bool> > dp(s.size(), vector<bool>(s.size(), false));
    // 确定递推公式
        // s[i] == s[j]
            // i与j相等或者相差1  直接赋true
            // i与j相差2及以上  查看dp[i + 1][j - 1]是否为true
        // s[i] != s[j]
            // dp[i][j] = false;
    // 初始化
        int result = 0;
    // 遍历顺序 为保证dp[i + 1][j - 1]都是被用到过的  所以遍历要从下到上  从左到右
        for(int i = s.size() - 1; i >= 0; i--){
            for(int j = i; j < s.size(); j++){
                if(s[i] == s[j]){
                    if(j - i <= 1){
                        result++;
                        dp[i][j] = true;
                    }else if(dp[i + 1][j - 1]){
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }
        return result;
    }
};


目录
打赏
0
0
0
0
1
分享
相关文章
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
101 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
76 0
|
6月前
|
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
38 1
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
|
6月前
|
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
55 0
【Leetcode刷题Python】73. 矩阵置零
|
6月前
|
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
本文介绍了LeetCode 478题的解法,题目要求在给定圆的半径和圆心位置的情况下实现在圆内均匀随机生成点的功能,并提供了Python的实现代码。
48 1
|
6月前
|
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
70 3
|
6月前
|
【Leetcode刷题Python】295. 数据流的中位数
本文介绍了一种使用Python实现的数据结构,用以支持数据流中添加整数并返回当前所有元素的中位数,通过排序列表来计算中位数。
48 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等