每日OJ题_回文串dp①_力扣647. 回文子串

本文主要是介绍每日OJ题_回文串dp①_力扣647. 回文子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

力扣647. 回文子串

解析代码

---

力扣647. 回文子串

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 由小写英文字母组成

class Solution {
public:int countSubstrings(string s) {}
};

---

解析代码

        这道题虽然动态规划的解法不是最优的解法（官方题解的中心拓展解法简单且空间是O（1），两种解法的时间都是O（N^2），但此题动态规划解法空间是O（N^2）），但是可以为后面的回文串dp类型的困难题做准备，思路就是可以先预处理一下，将所有子串是否回文的信息统计在 dp 表里面，然后直接在表里面统计 true 的个数即可。

        状态表示： 为了能表示出来所有的子串，我们可以创建⼀个 n * n 的二维 dp 表，只用到上三角部分即可。 其中， dp[i][j] 表示： s 字符串区间 [i, j] 的子串，是否是回文串。

状态转移方程：对于回文串，我们一般分析一个区间两头的元素：

当 s[i] != s[j] 的时候：不可能是回文串， dp[i][j] = 0 ;

当 s[i] == s[j] 的时候：根据长度分三种情况讨论：

• 长度为 1 ，也就是 i == j ：此时一定是回文串， dp[i][j] = true ;
• 长度为 2 ，也就是 i + 1 == j ：此时也一定是回文串， dp[i][j] = true ;
• 长度大于 2 ，此时要去看看 [i + 1, j - 1] 区间的子串是否回文： dp[i][j]= dp[i + 1][j - 1] ;

综上，状态转移方程分情况谈论即可。

分情况很细，无需初始化，填 j 用到 j - 1，所以从下往上填表，最后返回dp表中ture的个数。

class Solution {
public:int countSubstrings(string s) {int n = s.size(), ret = 0;vector<vector<bool>> dp(n, vector<bool>(n, false));// dp[i][j] 表示： s 字符串区间 [i, j] 的子串，是否是回文串for(int i = n - 1; i >= 0; --i){for(int j = i; j < n; ++j){if(s[i] == s[j])// if(i == j || i + 1 == j)dp[i][j] = i + 1 >= j ? true : dp[i + 1][j - 1] ;if(dp[i][j])++ret;}}return ret;}
};

这篇关于每日OJ题_回文串dp①_力扣647. 回文子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---