动态规划——回文串问题

ゞ浴缸里的玫瑰 2024-04-25 08:46 64阅读 0赞

**目录**

练习1：回文子串

练习2：最长回文子串

练习3：回文串分割IV

练习4：分割回文串

练习5：最长回文子序列

练习6：让字符串成为回文串的最小插入次数

--------------------

本篇文章主要学习使用动态规划来解决回文串相关问题，我们通过相关练习来学习

## 练习1：回文子串 ##

**题目链接：**

[647. 回文子串 - 力扣（LeetCode）][647. _ - _LeetCode]

**题目描述：**

给你一个字符串 `s` ，请你统计并返回这个字符串中 **回文子串** 的数目。

**回文字符串** 是正着读和倒过来读一样的字符串。

**子字符串** 是字符串中的由连续字符组成的一个序列。

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

**示例 1：**

输入：s = "abc"
    输出：3
    解释：三个回文子串: "a", "b", "c"

**示例 2：**

输入：s = "aaa"
    输出：6
    解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 由小写英文字母组成

**思路分析：**

题目要求我们统计字符串中 **回文子串** 的数目，其中，**具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串**。如例2所示：

![bd3d621acffe405b98524a329c314556.jpeg][]

选择前两个位置的字符，形成子串 "aa"，选择后两个位置的字符，形成子串"aa"，这两个子串虽然字符相同，但其开始 和 结束位置不同，因此，视作不同的子串

子串：字符串中的由**连续字符**组成的一个序列。

我们来分析状态表示

**状态表示：**

要统计字符串中回文子串的个数，就是要判断字符串的所有子串是否回文，如何判断呢？

要判断子串是否是回文，首先要找到所有子串，

> **表示出所有子串**

我们以 i 位置作为子串的起始位置，j 位置作为子串的结束位置

我们固定 i 位置，然后向后移动 j 位置，就可以枚举出 以 i 位置为起始的所有子串

![8e09a004d8df4c9584324db6293b2c90.jpeg][]

然后向后移动 i，继续向后枚举

![5dc89385301c43028a9db04de3a90d19.jpeg][]

因此，我们使用两层 for 循环，就可以枚举出字符串的所有子串，也就是说，我们用 一个二维数组就可以表示出所有情况

我们以**横坐标作为子串的起始位置，纵坐标作为子串的结束位置**：

![e7e03d3e7c8440269b1c0780c8557f60.jpeg][]dp\[i\]\[j\]：以 i 位置为起始，j 位置为结束的子串

由于起始位置 <= 结束位置，因此，我们只需要使用dp表中右上三角部分的空间就可以表示出所有子串

![0f43caf6c1fe438ebfbf5ecfec5a84e3.jpeg][]

接下来，我们判断子串是否是回文串

> **判断子串是否是回文串**

我们已经使用二维dp表表示出了所有情况，因此，我们只需要想办法在对应\[i, j\]位置上填上 true 或 false，就可以表示以 i 位置为起始，j位置为结束的字符是否是回文串了

因此，**dp\[i\]\[j\]：以 i 位置为起始，j位置为结束的子串是否是回文串**

**状态转移方程：**

![89f4d6d071ed476285cae4e45ac049e8.jpeg][]

要判断子串（从i位置到j位置）是否是回文串，首先要判断两端点（s\[i\] == s\[j\]）是否相同，

若两端的字符都不相同，则子串一定不是回文串

若两端点相同，我们还需分情况讨论：

> 若 i = j，则该子串只有一个字符，一定是回文串，dp\[i\]\[j\] = true
> 
> 若 i + 1 = j，该子串有两个字符且相同，一定是回文串，dp\[i\]\[j\] = true
> 
> 若 i + 1 < j，则该子串有多个字符，我们已经判断出两端点的字符相同，接下来，我们需要判断 \[i+1, j-1\]区间内的字符是否相同，即判断以 i + 1位置为起始，j - 1位置为结束的子串是否是回文串

![335b8d0c6d30450b8fec3eebeec3ddd4.jpeg][]

而 dp\[i+1\]\[j-1\] 表示 以 i + 1位置为起始，j - 1位置的子串是否是回文串，因此 dp\[i\]\[j\] = dp\[i+1\]\[j-1\]

因此，状态转移方程为：

![f14d8e7796bb41ecadad7a23c90dfe34.jpeg][]

**初始化：**

初始化要保证填表时不越界，但在填写dp表时，不会发生越界，因此我们无需初始化

**填表顺序：**

当 s\[i\] = s\[j\] 且 i + 1 < j 时，dp\[i\]\[j\] = dp\[i+1\]\[j-1\]

![e923c63864784cc6a4879970800f190f.jpeg][]

因此，在填写 \[i\]\[j\]位置时要保证\[i+1\]\[j-1\]位置已经填写，因此，需要**从下往上填写，而在填写每一行时，从左往右或从右往左都可以**

**返回值：**

要求回文子串的个数，因此，要**返回 dp 表中 true 的个数**

**代码实现：**

class Solution {
        public int countSubstrings(String s) {
            int n = s.length();
            int ret = 0;//统计回文子串的个数
            //创建dp表
            boolean[][] dp = new boolean[n][n];
            //初始化
            //填表
            for(int i = n - 1; i >= 0; i--){
                for(int j = i; j < n; j++){
                    if(s.charAt(i) == s.charAt(j)){
                        if(i == j || i + 1 == j) dp[i][j] = true;
                        else dp[i][j] = dp[i + 1][j - 1];
                    }
                    if(dp[i][j]) ret++;
                }
            }
            //返回
            return ret;
        }
    }

## 练习2：最长回文子串 ##

**题目链接：**

[5. 最长回文子串 - 力扣（LeetCode）][5. _ - _LeetCode]

**题目描述：**

给你一个字符串 `s`，找到 `s` 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

**示例 1：**

输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

**示例 2：**

输入：s = "cbbd"
    输出："bb"

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 仅由数字和英文字母组成

**思路分析：**

题目要求我们找到字符串中的最长回文子串。因此，我们首先要判断子串是否是回文串，然后再找到其中最长的回文子串

本题的解题思路与 **练习1：回文子串** 类似

我们可以使用二维dp表表示出所有情况，判断出所有子串是否为回文串

若 dp\[i\]\[j\] = true，则以 i 位置为起始，j 位置为结尾的子串是回文串，其长度为 j - i + 1

因此，我们只需找到**回文子串中 j - i + 1 的最大值**，即可找到最长的回文子串

**代码实现：**

class Solution {
        public String longestPalindrome(String s) {
            int n = s.length();
            int begin = 0, len = 1;//记录最长子串的起始位置和长度
            //创建dp表
            boolean[][] dp = new boolean[n][n];
            //初始化
            //填表
            for(int i = n - 1; i >= 0; i--){
                for(int j = i; j < n; j++){
                    if(s.charAt(i) == s.charAt(j)){
                        dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                    }
                    if(dp[i][j] && j - i + 1 > len){
                        len = j - i + 1;
                        begin = i;
                    }
                }
            }
            //返回
            return s.substring(begin, begin + len);
        }
    }

## 练习3：回文串分割IV ##

**题目链接：**

[1745. 分割回文串 IV - 力扣（LeetCode）][1745. _ IV - _LeetCode]

**题目描述：**

给你一个字符串 `s` ，如果可以将它分割成三个 **非空** 回文子字符串，那么返回 `true` ，否则返回 `false` 。

当一个字符串正着读和反着读是一模一样的，就称其为 **回文字符串** 。

**示例 1：**

输入：s = "abcbdd"
    输出：true
    解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

**示例 2：**

输入：s = "bcbddxy"
    输出：false
    解释：s 没办法被分割成 3 个回文子字符串。

**提示：**

*  `3 <= s.length <= 2000`
 *  `s` 只包含小写英文字母。

**思路分析：**

将字符串分割成三个非空字符串，若分割后三个子串都是回文串，则返回true，不能分割，则返回false

![931ff9e53a0f49dd91347304cd71274f.jpeg][]

设中间字符串的起始位置为 i，结束位置为 j

则划分后三个子串的区间分别为：**\[0, i - 1\] \[i, j\] \[j + 1, n-1\]**

此时，我们需要判断三个子串是否是回文串

同样的，我们可以使用二维dp表表示出所有情况，判断出所有子串是否为回文串

此时，判断这三个子串是否是回文串就变得非常简单了，**只需判断 dp\[0\]\[i - 1\]、dp\[i, j\] 和 dp\[j + 1\]\[n - 1\] 是否都为true**，就可以判断出这三个子串是否都是回文串了

因此，只需先判断所有子串是否是回文串，然后枚举第二个字符串所有的起始位置和结束位置，查询这三段非空子串是否是回文串即可

**代码实现：**

class Solution {
        public boolean checkPartitioning(String s) {
            int n = s.length();
            boolean[][] dp = new boolean[n][n];
            //判断所有子串是否是回文串
            for(int i = n - 1; i >= 0; i--){
                for(int j = i; j < n; j++){
                    if(s.charAt(i) == s.charAt(j)) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }
            //枚举第二个字符串的所有起始位置和结束位置
            for(int i = 1; i < n - 1; i ++){
                for(int j = i; j < n - 1; j++){
                    if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;
                }   
            }
            return false;
        }
    }

## 练习4：分割回文串 ##

**题目链接：**

[132. 分割回文串 II - 力扣（LeetCode）][132. _ II - _LeetCode]

**题目描述：**

给你一个字符串 `s`，请你将 `s` 分割成一些子串，使每个子串都是回文串。

返回符合要求的 **最少分割次数** 。

**示例 1：**

输入：s = "aab"
    输出：1
    解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

**示例 2：**

输入：s = "a"
    输出：0

**示例 3：**

输入：s = "ab"
    输出：1

**提示：**

*  `1 <= s.length <= 2000`
 *  `s` 仅由小写英文字母组成

**思路分析：**

要求将字符串分割成子串的最少分割次数

**状态表示：**

我们首先以 i 位置为结尾进行分析：

则 **dp\[i\]： \[0, i\]区间内的最少分割次数**

**状态转移方程：**

若 以 0 位置为起始，i位置为结尾的子串是回文串，此时不需要分割，dp\[i\] = 0

而 以 0 位置为起始，i位置为结尾的子串不是回文串时，我们根据前面的状态来推导 dp\[i\]

假设我们在 j 位置进行分割，则分割出 以 j 位置为起始，i 位置为结尾的子串，若这个子串是回文串

![d3bafd65859d4b5dadeb17e813b61e36.jpeg][]

则 我们只需要考虑 \[0, j - 1\]区间内分割了多少词（dp\[j - 1\]），再加上这一次，就可以 得到 dp\[i\]

因此，我们先考虑最后一次分割：

假设在 j 位置进行分割**（0 < j <= i）**，然后判断 从 j 到 i 这个子串是否是回文串：

若 是 回文串，则 **dp\[i\] = dp\[j - 1\] + 1**

若 不是 回文串，此时这种分割方式不合理，不考虑

我们要求最小分割次数，因此 我们要求能够分割的情况中的最小值（即min(dp\[j - 1\] + 1)）

在此过程中，我们需要判断 \[0, i \] 区间子串是否是回文，\[j, i\]区间子串是否是回文，因此，我们同样可以使用 二维dp表，判断所有子串是否是回文串

![116fc9dd6a564500b71ea39ca7d4ab5a.jpeg][]

**初始化：**

初始化要保证填表时不越界，当 j = 0时可能会越界，但 j 不可能为 0，因此不会发生越界，但由于我们要求 dp\[i\]的最小值，因此我们可以**将所有的值都初始化为最大值**

**填表顺序：**

填写 dp\[i\] 时，要保证 dp\[j - 1\]已经填写，j - 1 在 i 位置之前，因此 填表顺序为**从左到右**

**返回值：**

dp\[i\] ：0 到 i 位置的最小分割次数，要求字符串的最小分割次数，因此**返回 dp\[n - 1\]**

**代码实现：**

class Solution {
        public int minCut(String s) {
            //预处理
            int n = s.length();
            boolean[][] isPal = new boolean[n][n];
            for(int i = n - 1; i >= 0; i--){
                for(int j = i; j < n; j++){
                    if(s.charAt(i) == s.charAt(j)) isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
                }
            }
            //创建dp表
            int[] dp = new int[n];
            //初始化
            for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;
            //填表
            for(int i = 0; i < n; i++){
                if(isPal[0][i]) dp[i] = 0;
                else{
                    for(int j = 1; j <= i; j++){
                        if(isPal[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
            //返回
            return dp[n - 1];
        }
    }

## 练习5：最长回文子序列 ##

**题目链接：**

[516. 最长回文子序列 - 力扣（LeetCode）][516. _ - _LeetCode]

**题目描述：**

给你一个字符串 `s` ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

**示例 1：**

输入：s = "bbbab"
    输出：4
    解释：一个可能的最长回文子序列为 "bbbb" 。

**示例 2：**

输入：s = "cbbd"
    输出：2
    解释：一个可能的最长回文子序列为 "bb" 。

**提示：**

*  `1 <= s.length <= 1000`
 *  `s` 仅由小写英文字母组成

**思路分析：**

本题与前面的题不同，要求的是**最长回文序列**，**子串，是连续的字符串**，而**子序列，可以是连续的，也可以是不连续的，**是在不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

**状态表示：**

我们首先以 i 位置为结尾进行分析，则 **dp\[i\]：以 i 位置为结尾的所有子序列中，最长的回文子序列的长度**

接着，我们来分析状态转移方程：

我们需要根据前面的状态来推导dp\[i\]，我们以 i - 1位置进行分析，但是 dp\[i - 1\] ：以 i 位置为结尾的所有子序列中，最长的回文子序列的长度，我们**不知道回文子序列是怎样的，不能确定添加s\[i\]后是否依旧是回文子序列，因此无法确定dp\[i\]**

我们再考虑其他方法

若 以 i 位置为起始，j 位置为结尾的子串是回文串，在这个子串的左右加上相同的字符，新的子串依旧是回文串

则，若\[i + 1, j - 1\]内存在最长回文子序列，则

![b1675d7ba7424bd7b9092fd0b5807934.jpeg][]

若s\[i\] == s\[j\]，则最长回文子序列长度 + 2，则\[i, j\]区间内的最长回文子序列长度 = \[i + 1, j - 1\]区间内最长回文子序列长度 + 2，因此我们可以根据\[i+1, j - 1\]区间内的最长回文子序列长度，推导出\[i, j\]区间内最长回文子序列的长度

我们根据这个思路来定义状态表示：

**dp\[i\]\[j\]：字符串\[i, j\]区间内的最长回文子序列长度**

接下来，我们分析状态转移方程

**状态转移方程：**

我们以 i 位置为起始，j 位置为结束

若 s\[i\] = s\[j\]，则 dp\[i\]\[j\] = dp\[i + 1\]\[j - 1\] + 1，但前提条件是dp\[i + 1\]\[j - 1\]存在，因此，我们需要分情况讨论：

> 若 i = j，则\[i, j\]区间内只有一个字符，则 最长回文子序列长度为 1
> 
> 若 i + 1 = j，则\[i, j\]区间内有两个相同的字符，则 最长回文子序列长度为 2
> 
> 若 i + 1 < j，则\[i, j\]区间内有多个字符，则只需要在\[i + 1, j - 1\]区间内找到最长回文子序列长度，然后再 + 2，即 dp\[i + 1\]\[j - 1\] + 2

若 s\[i\] != s\[j\]，则最长回文子序列一定不可能 以 i 位置为起始，以 j 位置为结束，因此，我们可以在\[i, j - 1\]内找最长回文子序列长度，然后在\[i + 1, j\]区间内找最长回文子序列长度，最后取其中的较大值，即 max(dp\[i, j - 1\], dp\[i + 1, j\])

![55d352bc8c394fe59ece838e0ddda3d4.jpeg][]

因此，状态转移方程为：

![3ee870186f3a407088f35f8bc8f71a2c.jpeg][]

**初始化：**

由于在填表时不会发生越界，因此**无需初始化**

**填表顺序：**

由于 i <= j，因此只会填写：

![0bb5d3148be340dda273119dd5de0a33.png][]

在填写dp\[i\]\[j\]时，需要 dp\[i + 1\]\[j - 1\]、dp\[i\]\[j - 1\] 和 dp\[i - 1\]\[j\]

![edf3b68a2598485ca848b7cecfa8cf6b.jpeg][]

因此，我们首先要保证**从下往上**填写，在填写时需要用到左边的值，因此在填写每一行时，要**从左往右**填写

**返回值：**

dp\[i\]\[j\]： 字符串\[i, j\]区间内的最长回文子序列长度，而需要求字符串的最长回文子序列长度，即起始位置为0，结束位置为 n - 1，因此，返回**dp\[0\]\[n - 1\]**

**代码实现：**

class Solution {
        public int longestPalindromeSubseq(String s) {
            int n = s.length();
            //创建dp表
            int[][] dp = new int[n][n];
            //初始化
            //填表
            for(int i = n - 1; i >= 0; i--){
                for(int j = i; j < n; j++){
                    if(s.charAt(i) == s.charAt(j)){
                        if(i == j) dp[i][j] = 1;
                        else if(i + 1 == j) dp[i][j] = 2;
                        else dp[i][j] = dp[i + 1][j - 1] + 2;
                    }else{
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                    }
                    
                }
            }
            //返回
            return dp[0][n - 1];
        }
    }

## 练习6：让字符串成为回文串的最小插入次数 ##

**题目链接：**

[1312. 让字符串成为回文串的最少插入次数 - 力扣（LeetCode）][1312. _ - _LeetCode]

**题目描述：**

给你一个字符串 `s` ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 `s` 成为回文串的 **最少操作次数** 。

「回文串」是正读和反读都相同的字符串。

**示例 1：**

输入：s = "zzazz"
    输出：0
    解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

**示例 2：**

输入：s = "mbadm"
    输出：2
    解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

**示例 3：**

输入：s = "leetcode"
    输出：5
    解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

**提示：**

*  `1 <= s.length <= 500`
 *  `s` 中所有字符都是小写字母。

**思路分析：**

题目要求我们在字符串中插入字符使其成为回文串，要求出最少插入次数

**状态表示：**

与 **练习5：最长回文子序列** 类似，当我们选择以 i 位置为结尾时，很难推出状态转移方程，因此，我们以 \[i, j\]区间来研究问题（i <= j）

**dp\[i\]\[j\]：\[i, j\]区间内，使其成为回文串的最小插入次数**

**状态转移方程：**

我们根据最后一步来划分问题，也就是根据两个端点（i，j）来划分问题：

若 s\[i\] = s\[j\]：

> 若 i = j，则\[i, j\]区间内只有一个字符，此时已经是回文串了，插入次数为0
> 
> 若 i + 1 = j，则\[i, j\]区间内有两个字符相同的字符，此时也是回文串了，插入次数为 0
> 
> 若 i + 1 < j，则\[i, j\]区间内有多个字符，由于s\[i\] = s\[j\]，因此两端字符不用考虑，只需考虑\[i + 1, j - 1\]区间内的最小插入次数，即 dp\[i + 1\]\[j - 1\]

若 s\[i\] != s\[j\]：

此时我们在\[i, j\]区间的最左边添加上字符s\[j\]，就可以与 最右边的s\[j\]匹配，此时，我们只需考虑\[i, j - 1\]区间内的最小操作次数，即 dp\[i\]\[j - 1\]，然后再加上此时添加的一个字符，即 dp\[i\]\[j - 1\] + 1

![862ab085ffb5408496289925308b39fb.jpeg][]

同样的，在最右边添加上字符s\[i\]，就可以和最左边的s\[i\]匹配，此时只需考虑\[i + 1, j\]区间内的最小操作次数，即 dp\[i + 1\]\[j\]，然后再加上此时添加的一个字符，即 dp\[i + 1\]\[j\] + 1

要最小操作次数，只需取最小值，min(dp\[i + 1\]\[j\] + 1, dp\[i\]\[j - 1\] + 1)

因此，状态转移方程为：

![07ef4755edca4ae8aa8c699fc48b1a75.jpeg][]

**初始化：** 由于在填表时不会发生越界，因此**无需初始化**

**填表顺序：**

在填写dp\[i\]\[j\]时，需要 dp\[i + 1\]\[j - 1\]、dp\[i\]\[j - 1\] 和 dp\[i - 1\]\[j\]

![edf3b68a2598485ca848b7cecfa8cf6b.jpeg][]

因此，我们首先要保证**从下往上**填写，在填写时需要用到左边的值，因此在填写每一行时，要**从左往右**填写

**返回值：**

dp\[i\]\[j\]：\[i, j\]区间内，使其成为回文串的最小插入次数，而需要求字符串成为回文串的最少插入次数，即起始位置为0，结束位置为 n - 1，因此，**返回dp\[0\]\[n - 1\]**

**代码实现：**

class Solution {
        public int minInsertions(String s) {
            int n = s.length();
            //创建dp表
            int[][] dp = new int[n][n];
            //填表
            for(int i = n-1; i >= 0; i--){
                for(int j = i + 1; j < n; j++){//i = j的时候,dp[i][j] = 0,因此无需再考虑
                    if(s.charAt(i) == s.charAt(j)){
                        dp[i][j] = dp[i+1][j-1];
                    }else{
                        dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i + 1][j] + 1);
                    }
                }
            }
            //返回
            return dp[0][n - 1];
        }
    }

[647. _ - _LeetCode]: https://leetcode.cn/problems/palindromic-substrings/description/
[bd3d621acffe405b98524a329c314556.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/859b9c69e67c41a08baa12aa80c80f00.jpeg
[8e09a004d8df4c9584324db6293b2c90.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/3d743944d5f5413eadaab4eaaeb0cfd6.jpeg
[5dc89385301c43028a9db04de3a90d19.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/3b45a6c5ba7c45adb1faaf1f51b6b470.jpeg
[e7e03d3e7c8440269b1c0780c8557f60.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/9f098f92a1164a74a2f118c93a5c8ac6.jpeg
[0f43caf6c1fe438ebfbf5ecfec5a84e3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/89318f1268924ee6adb258452792f18b.jpeg
[89f4d6d071ed476285cae4e45ac049e8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/6df9998b5ed9438f942c7817de5e81c8.jpeg
[335b8d0c6d30450b8fec3eebeec3ddd4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/b7ea6ebe02204249a7b41a4cc466fda9.jpeg
[f14d8e7796bb41ecadad7a23c90dfe34.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/467e47dc0c21461da33510983c7c9db6.jpeg
[e923c63864784cc6a4879970800f190f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/69b560fc19f246df8a727fe1da6fc453.jpeg
[5. _ - _LeetCode]: https://leetcode.cn/problems/longest-palindromic-substring/description/
[1745. _ IV - _LeetCode]: https://leetcode.cn/problems/palindrome-partitioning-iv/description/
[931ff9e53a0f49dd91347304cd71274f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/0b8aabad8c7742ae83fe0c8467ae6865.jpeg
[132. _ II - _LeetCode]: https://leetcode.cn/problems/palindrome-partitioning-ii/description/
[d3bafd65859d4b5dadeb17e813b61e36.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/3b0ba2ccc93d40f495d682283f14a44e.jpeg
[116fc9dd6a564500b71ea39ca7d4ab5a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/8c8add6b62394a7a9942abc1b324f405.jpeg
[516. _ - _LeetCode]: https://leetcode.cn/problems/longest-palindromic-subsequence/description/
[b1675d7ba7424bd7b9092fd0b5807934.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/bd6b2e3aac644e24ade094aba45ff491.jpeg
[55d352bc8c394fe59ece838e0ddda3d4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/1c6239284b834eccb8f5225287d87ace.jpeg
[3ee870186f3a407088f35f8bc8f71a2c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e54dcf02503247ba8fa7944ac786034e.jpeg
[0bb5d3148be340dda273119dd5de0a33.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c017431881e847abaf0d2b046c75224d.png
[edf3b68a2598485ca848b7cecfa8cf6b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/0f15df4efc30470491fdae75086e83bb.jpeg
[1312. _ - _LeetCode]: https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
[862ab085ffb5408496289925308b39fb.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/f6e2b62d71314064a5533909974a3a52.jpeg
[07ef4755edca4ae8aa8c699fc48b1a75.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/8527bc31671641ac81d7f97365043cd9.jpeg