动态规划-647.回文子串-力扣(LeetCode)

一、题目解析

这里的子字符串是连续的，与之前的子序列不同，这里需要我们统计回文子串的数目。

二、算法原理

这里也有其他算法可以解决该问题，如中心扩展算法 时间复杂度O(N^2)/空间复杂度O(1)，马拉车算法(具有局限性) 时间复杂度O(N)/空间复杂度O(N)，动态规划 时间复杂度O(N^2)/空间复杂度O(N^2)

我们这里使用动态规划，可以将所有子串是否回文的结果保存在dp表中，通过统计dp就能得到回文子串的数目。

1.状态表示

dp[i][j]：表示s字符串[i,j]的子串，是否为回文子串

2.状态转移方程

 根据最后一步划分状态，s[i]与s[j]是否相等，如不等，则子串不为回文子串；如相等则继续判断

dp[i][j] s[i] != s[j]->false

           s[i] == s[j] i == j->true

                            i+1=j->true

                           dp[i+1][j-1]

这里不会出现越界行为，首先状态表示定义的是[i,j]范围的子串，其次上面包括了相邻和相等的情况，所以是不会有越界问题的

3、初始化

由于我们填写的是bool值，不需要初始化

4、填表顺序

 

5、返回值

我们已经统计好了是否为回文子串，所以只需要记录dp表中true的数量即可。

 这种思路同样适用于其他回文子串问题，建议理解后自己动手实现

647. 回文子串 - 力扣（LeetCode）

三、代码示例

class Solution {
public:int countSubstrings(string s) {int n = s.size();vector<vector<bool>> dp(n,vector<bool>(n));for(int i = n-1;i>=0;i--){for(int j = i;j<n;j++){if(s[i] != s[j]) dp[i][j] = false;else{if(i == j) dp[i][j] = true;else if(i+1 == j) dp[i][j] = true;else dp[i][j] = dp[i+1][j-1];}}}int ret = 0;for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){if(dp[i][j]) ret++;}}return ret;}
};

 

看到最后，如果对您有所帮助，还请点赞、收藏和关注，点点关注不迷路，我们下期再见！