回文子串(LeetCode-647)

简介: 回文子串(LeetCode-647)

回文子串(LeetCode-647)


题目

给你一个字符串 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[i][j] 含义


区间范围为 [ i , j ] (注意左右都是闭区间)的子串是否为回文子串,元素类型为布尔类型

递推公式


当 s [ i ] ≠ s [ j ] 时,元素值必为 f a l s e

当 s [ i ] = s [ j ] 时,分三种情况

情况一:i = j ,即二者下标相等,都指向同一个字符,肯定是回文子串

情况二:i 和 j  下标相差 1 ,例如 a a,也是回文子串

情况三:二者下标相差大于一,那必须看区间 s [ i + 1 , j − 1 ]是不是回文子串

数组初始化


初始值全为 f a l s e

遍历顺序

要注意看当前元素依靠谁的状态获取,看到前文情况三,就知道肯定对于 i ii 的遍历肯定要倒序。


代码展示

class Solution
{
public:
    int countSubstrings(string s)
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int result = 0;
        for (int j = 0; j < n; j++)
        {
            for (int i = j; i >= 0; i--)
            {
                if (s[i] == s[j])
                {
                    if (j - i <= 1)
                    {
                        dp[i][j] = true;
                        result++;
                    }
                    else
                    {
                        if (dp[i + 1][j - 1])
                        {
                            dp[i][j] = true;
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
};
目录
相关文章
|
监控 Shell Linux
【Shell 命令集合 系统管理 】⭐⭐⭐Linux 向进程发送信号 kill命令 使用指南
【Shell 命令集合 系统管理 】⭐⭐⭐Linux 向进程发送信号 kill命令 使用指南
294 0
|
Java
Java操作时间工具类
Java操作时间工具类
210 0
|
Docker 容器 Linux
幻兽帕鲁存档迁移问题心得_告别存档丢失_进入就掉线
你是不是也遇到了存档文件迁移后,还是让你创建新角色,或者是迁移后没几秒就掉线,我也遇到了一样的问题,花了好半天终于解决了,这里记录分享一下。
8241 4
幻兽帕鲁存档迁移问题心得_告别存档丢失_进入就掉线
|
Java API 数据库
thymeleaf 中 通用的分页方法
thymeleaf 中 通用的分页方法
190 0
|
Web App开发 存储 移动开发
Uncaught (in promise) DOMException: The play() request was interrupted by a new load request.异常处理
Uncaught (in promise) DOMException: The play() request was interrupted by a new load request.异常处理
1457 0
|
前端开发 JavaScript 容器
[后端浅了解]基本标签详解03
[后端浅了解]基本标签详解03
|
前端开发 Java API
集成Swagger 学习(一)
集成Swagger 学习(一)
208 0
|
算法 程序员 数据处理
轻轻松松学会Python入门三:经典实例-温度转换
为了希望让大家能够很快的上手,并且印象深刻,我们先提出一个例子。该例子包含了学习Python初期的一些基本知识点,大家需要先对这些东西有一些基本的了解。
218 0
轻轻松松学会Python入门三:经典实例-温度转换
【CS50x】Runoff 题解(上)
【CS50x】Runoff 题解(上)
479 0
【CS50x】Runoff 题解(上)