算法系列--动态规划--回文子串系列（上）
https://developer.aliyun.com/article/1480805?spm=a2c6h.13148508.setting.14.5f4e4f0e5BpQyj
💕"我们好像在池塘的水底，从一个月亮走向另一个月亮。。"💕
作者：Mylvzi
文章主要内容：算法系列–动态规划–回文子串系列
今天为大家带来的是
算法系列--动态规划--回文子串系列(1),本文重点掌握如何快速判断一个字符串是否是回文子串
3.回⽂串分割IV
链接:
https://leetcode.cn/problems/palindrome-partitioning-iv/description/
分析:
- 其实题目的意思很简单,就是
判断字符串s能否分割为三个回文子串,最直观的想法就是暴力求解+判断是否是回文子串,而判断是否是回文子串已经在上面做过了
代码:
class Solution { public boolean checkPartitioning(String s) { char[] ss = s.toCharArray();// 转化为字符数组 int ret = 0;// 记录dp表中true的数目 int n = s.length(); boolean[][] dp = new boolean[n][n]; // 使用dp表保存所有的子字符串的信息 for(int i = n - 1; i >= 0; i--) {// 从后往前遍历字符串 for(int j = i; j < n; j++) { if(ss[i] == ss[j])// 只用判断相等的情况,不相等就是默认值false; dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true; } } // 将字符串s分割为三个子字符串,分别判断是否是回文字符串 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.分割回⽂串II
链接:
https://leetcode.cn/problems/palindrome-partitioning-ii/description/
分析:
其实这道题和单词拆分很像,单词拆分中需要我们遍历整个字符串,判断对应的单词是否存在于字典之中,本题也是需要遍历整个字符串,判断对应的子字符串是否是回文子串,而判断是否是回文子串已经在上面介绍过
代码:
class Solution { public int minCut(String s) { char[] ss = s.toCharArray();// 转化为字符数组 int ret = 0;// 记录dp表中true的数目 int n = s.length(); boolean[][] predp = new boolean[n][n]; for(int i = n - 1; i >= 0; i--) {// 从后往前遍历字符串 for(int j = i; j < n; j++) { if(ss[i] == ss[j])// 只用判断相等的情况,不相等就是默认值false; predp[i][j] = i + 1 < j ? predp[i + 1][j - 1] : true; } } // 下面是正题 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(predp[0][i] == true) dp[i] = 0;// 0->i为回文串 else {// 0->i不是回文串 for(int j = 1; j <= i; j++) { if(predp[j][i]) dp[i] = Math.min(dp[i],dp[j - 1] + 1); } } } return dp[n - 1]; } }
5.最长回文子序列
链接:
https://leetcode.cn/problems/longest-palindromic-subsequence/
分析:
最先想到的状态表示就是以i位置为结尾字符串中的最长的回文子序列的长度,但是进一步分析发现此状态表示无法推导出状态转移方程,原因在于我们根本不能确定回文子序列,所以要更换一个状态表示
经过上述分析发现仅仅固定一个位置去表示字符串无法确定其回文子序列,所以需要两个下标来确定一个字符串(是不是和回文子串很像?),然后再去推导状态转移方程,只不过这里的状态相较于连续的子串更多一些,下面是详细的分析过程
代码:
class Solution { public int longestPalindromeSubseq(String s) { char[] ss = s.toCharArray();// 转化为字符数组 int n = s.length(); // 创建dp表 int[][] dp = new int[n][n]; dp[0][0] = dp[n - 1][n - 1] = 1;// 初始化 int ret = 0;// 记录最大值 for(int i = n -1; i >=0; i--) { for(int j = i; j < n; j++) { if(ss[i] == ss[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 + 1][j],dp[i][j - 1]); } ret = ret > dp[i][j] ? ret : dp[i][j];// 更新最值 } } return ret; } }
6.让字符串成为回⽂串的最⼩插⼊次数（hard）
链接:
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
分析:
代码:
class Solution { public int minInsertions(String s) { char[] ss = s.toCharArray();// 转化为字符数组 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(ss[i] == ss[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : 0; else dp[i][j] = Math.min(dp[i + 1][j],dp[i][j - 1]) + 1; } } return dp[0][n - 1]; } }
