647.回文子串

冷不防 2024-03-01 08:12 64阅读 0赞

#### 647.回文子串 ####

*  题干分析
 *  解题思路
 *   *  1. 确定dp数组（dp table）以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  其他解题思路（双指针法）
 *  代码实现
 *   *  1. 动态规划法
     *  2. 中心扩散法

## 题干分析 ##

[力扣入口][Link 1]  
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

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

示例 1：

*  输入：“abc”
 *  输出：3
 *  解释：三个回文子串: “a”, “b”, “c”

示例 2：

*  输入：“aaa”
 *  输出：6
 *  解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：输入的字符串长度不会超过 1000 。

## 解题思路 ##

### 1. 确定dp数组（dp table）以及下标的含义 ###

如果大家做了很多这种子序列相关的题目，在定义dp数组的时候 很自然就会想题目求什么，我们就如何定义dp数组。

绝大多数题目确实是这样，不过本题如果我们定义，dp\[i\] 为 下标i结尾的字符串有 dp\[i\]个回文串的话，我们会发现很难找到递归关系。

dp\[i\] 和 dp\[i-1\] ，dp\[i + 1\] 看上去都没啥关系。

所以我们要看回文串的性质。 如图：  
![在这里插入图片描述][66cef07893fe4022b91a199379d9abbf.png]  
我们在判断字符串S是否是回文，那么如果我们知道 s\[1\]，s\[2\]，s\[3\] 这个子串是回文的，那么只需要比较 s\[0\]和s\[4\]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。

那么此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串的下表范围\[i,j\]）是否回文，依赖于，子字符串（下表范围\[i + 1, j - 1\]）） 是否是回文。

所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。

**布尔类型的dp\[i\]\[j\]：表示区间范围\[i,j\] （注意是左闭右闭）的子串是否是回文子串，如果是dp\[i\]\[j\]为true，否则为false。**

### 2. 确定递推公式 ###

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s\[i\]与s\[j\]相等，s\[i\]与s\[j\]不相等这两种。

当s\[i\]与s\[j\]不相等，那没啥好说的了，dp\[i\]\[j\]一定是false。

当s\[i\]与s\[j\]相等时，这就复杂一些了，有如下三种情况

*  情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
 *  情况二：下标i 与 j相差为1，例如aa，也是回文子串
 *  情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s\[i\]与s\[j\]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp\[i + 1\]\[j - 1\]是否为true。

以上三种情况分析完了，那么递归公式如下：

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;
        }
    }

result就是统计回文子串的数量。

注意这里我没有列出当s\[i\]与s\[j\]不相等的时候，因为在下面dp\[i\]\[j\]初始化的时候，就初始为false。

### 3. dp数组如何初始化 ###

dp\[i\]\[j\]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。

所以dp\[i\]\[j\]初始化为false。

### 4. 确定遍历顺序 ###

遍历顺序可有有点讲究了。

首先从递推公式中可以看出，情况三是根据dp\[i + 1\]\[j - 1\]是否为true，在对dp\[i\]\[j\]进行赋值true的。

dp\[i + 1\]\[j - 1\] 在 dp\[i\]\[j\]的左下角，如图：  
![在这里插入图片描述][3d13c57de4f6454e8e5e66a9d8df8d78.png]  
如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp\[i + 1\]\[j - 1\]，也就是根据不确定是不是回文的区间\[i+1,j-1\]，来判断了\[i,j\]是不是回文，那结果一定是不对的。

**所以一定要从下到上，从左到右遍历，这样保证dp\[i + 1\]\[j - 1\]都是经过计算的。**

有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证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;
                }
            }
        }
    }

### 5. 举例推导dp数组 ###

举例，输入：“aaa”，dp\[i\]\[j\]状态如下：  
![在这里插入图片描述][97fcabcdac3f4e67b5325cbba8bf9de7.png]  
图中有6个true，所以就是有6个回文子串。

注意因为dp\[i\]\[j\]的定义，所以j一定是大于等于i的，那么在填充dp\[i\]\[j\]的时候一定是只填充右上半部分。

## 其他解题思路（双指针法） ##

动态规划的空间复杂度是偏高的，我们再看一下双指针法。

首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。

**在遍历中心点的时候，要注意中心点有两种情况。**

一个元素可以作为中心点，两个元素也可以作为中心点。

那么有人同学问了，三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。

所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。

## 代码实现 ##

### 1. 动态规划法 ###

class Solution {
        
        // 647.回文子串 - 动态规划法
        public int countSubstrings(String s){
        
            boolean[][] dp = new boolean[s.length()][s.length()];
            int res = 0;
            for(int i = s.length() - 1; i >= 0; i--){
        
                for(int j = i; j < s.length(); j++){
        
                    if(s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])){
        
                        res++;
                        dp[i][j] = true;
                    }
                }
            }
            return res;
        }
    }

### 2. 中心扩散法 ###

class Solution {
        
        // 647.回文字串 - 中心扩散法
        public int countSubstrings(String s){
        
            int len, ans = 0;
            if(s == null || (len = s.length()) < 1) return 0;
            // 总共有2 * len - 1个中心点
            for (int i = 0; i < 2 * len - 1; i++) {
        
                //通过遍历每个回文中心，向两边扩散，并判断是否回文字串
                //有两种情况，left == right，right = left + 1，这两种回文中心是不一样的
                int left = i / 2, right = left + i % 2;
                while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
        
                    //如果当前是一个回文串，则记录数量
                    ans++;
                    left--;
                    right++;
                }
            }
            return ans;
        }
    }

**参考资料**：[代码随想录-647. 回文子串][-647.]

[Link 1]: https://leetcode.cn/problems/palindromic-substrings/
[66cef07893fe4022b91a199379d9abbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/1f59bf9d026b4bde844636d61c250f54.png
[3d13c57de4f6454e8e5e66a9d8df8d78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/c2723373177c417ba332b3fc97caaad5.png
[97fcabcdac3f4e67b5325cbba8bf9de7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/9779db6cd2bf400081af44fc82092555.png
[-647.]: https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE