LeetCode动态规划编辑距离问题——647.回文子串

左手的ㄟ右手 2023-10-03 19:28 59阅读 0赞

#### **题目描述：** ####

[647. 回文子串][647.]

给你一个字符串 `s` ，请你统计并返回这个字符串中 **回文子串** 的数目。**回文字符串** 是正着读和倒过来读一样的字符串。**子字符串** 是字符串中的由连续字符组成的一个序列。

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

![fa2f1a8cd84249cfb1f7e7b2187f8565.png][]

#### **分析：** ####

牢记动态规划五步：

1.确定dp数组含义

2.确定递推公式

3.dp数组初始化

4.确定遍历顺序

01背包问题：一维dp的遍历，商品放在外循环，背包在内循环，且内循环倒序。

求组合：先遍历商品，再遍历背包

求排列：先便利背包，再遍历商品

求最大最小：对遍历顺序没有要求

5.举列推导

#### **代码：** ####

**动态规划版本：**

class Solution {
        public int countSubstrings(String s) {
            int len, ans = 0;
            if (s == null || (len = s.length()) < 1) return 0;
            //dp[i][j]：s字符串下标i到下标j的字串是否是一个回文串，即s[i, j]
            boolean[][] dp = new boolean[len][len];
            for (int j = 0; j < len; j++) {
                for (int i = 0; i <= j; i++) {
                    //当两端字母一样时，才可以两端收缩进一步判断
                    if (s.charAt(i) == s.charAt(j)) {
                        //i++，j--，即两端收缩之后i,j指针指向同一个字符或者i超过j了,必然是一个回文串
                        if (j - i < 3) {
                            dp[i][j] = true;
                        } else {
                            //否则通过收缩之后的字串判断
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    } else {//两端字符不一样，不是回文串
                        dp[i][j] = false;
                    }
                }
            }
            //遍历每一个字串，统计回文串个数
            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (dp[i][j]) ans++;
                }
            }
            return ans;
        }
    }

#### 本题使用中心扩展法更合适： ####

class Solution {
        public int countSubstrings(String s) {
            int count=0;//用于统计回文子串的数目
            //一个长度为n的字符串可以有2n-1个中心点（可以以一个字符或两个连续字符作为中心点）
            for(int i=0;i<2*s.length()-1;i++){
                //当i为奇数时，以一个字符为中心点，为偶数时以两个连续字符为中心点
               int left=i/2;
               int right=i/2+i%2;
               while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
                 left--;
                 right++;
                 count++;
               }
            }
            return count;
        }
    }

#### 动态规划做题方法： ####

做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp\[i\]表示的是什么。这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。 确定递推公式仅仅是动态规划解题的一步！知道递推公式，但不知道dp数组要怎么初始化，数组要怎么正确的遍历

所以，我们始终牢记动态规划五步：

1.确定dp数组含义

2.确定递推公式

3.dp数组初始化

4.确定遍历顺序

5.举例推导

做题之前，可以自己先思考这三个问题：

*  这道题目我举例推导状态转移公式了么？
 *  我举例推导dp数组了嘛？
 *  打印出来的dp数组和我想的一样么？

后序的跟着博主解题，大家就会慢慢感受到这五步的重要性了。

博主会持续更新LeetCode的题解和Java学习过程的问题噢（都按照题型进行分类啦~），如果对你有帮助的话，请帮博主点个赞，关注博主一起成长吧！

[647.]: https://leetcode.cn/problems/palindromic-substrings/
[fa2f1a8cd84249cfb1f7e7b2187f8565.png]: https://img-blog.csdnimg.cn/fa2f1a8cd84249cfb1f7e7b2187f8565.png