💕"我们好像在池塘的水底，从一个月亮走向另一个月亮。。"💕
作者：Mylvzi
文章主要内容：算法系列–动态规划–回文子串系列
今天为大家带来的是
算法系列--动态规划--回文子串系列(1),本文重点掌握如何快速判断一个字符串是否是回文子串
一.回文子串(引入)
先来看力扣上这道题目:回文子串
1.利用动态规划的思想解决这道题目(重点)
回文子串其实是子数组的一种,只不过这里将数字换为字符而已,所以回文子串的问题也可以使用动态规划的思想解决,但是这个状态表示相较于常规的字符数组有些不同,在回文子串问题中,我们需要创建一个二维的dp表去存储所有子串是否是回文子串的信息,也就是说这个dp表是一个`boolean``类型的数组
首先如何得到所有的子字符串呢?很简单,两层for循环就能解决这个问题
注意:单独一个字符也算子字符串!!!
明确上述前置知识之后,下面讲解如何利用动态规划的思想解决回文子串问题
- 状态表示:dp[i][j]表示
以i下标为起始位置,j下标为结束位置的子字符串是否是回文子串的信息 - 状态转移方程:
- 初始化:
无需初始化,越界的条件被特别判断了,不会出现越界的情况
- 填表顺序:
从下往上填
- 返回值:
dp[i][j]为true的数目
代码实现:
class Solution { public int countSubstrings(String s) { char[] ss = s.toCharArray();// 转化为字符数组 int ret = 0;// 记录dp表中true的数目 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(ss[i] == ss[j])// 只用判断相等的情况,不相等就是默认值false; dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true; ret += dp[i][j] == true ? 1 : 0; } } return ret; } }
如果使用动态规划,时间复杂度,空间复杂度均为为O(N^2)回文子串问题使用动态规划虽然不是最优解,但是可以实现一个非常重要的功能将所有子串是否是回文子串的信息,存储到dp表之中,最优解还有中心拓展算法和马拉车算法
中心拓展算法的实现:
来源：力扣（LeetCode）
class Solution { public int countSubstrings(String s) { int n = s.length(), ans = 0; for (int i = 0; i < 2 * n - 1; ++i) { int l = i / 2, r = i / 2 + i % 2; while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { --l; ++r; ++ans; } } return ans; } }
2.最长回文子串
链接:
https://leetcode.cn/problems/longest-palindromic-substring/
分析:
还是利用和上道题一样的动态规划思想,在本题中需要得到的是最长的回文子串,在回文子串的动态规划里,我们已经保存了所有的回文子串的信息,只要判断出来时回文子串,就更新一下长度即可
可以使用一个数组ret来记录字符串的起始结束位置
代码:
class Solution { public String longestPalindrome(String s) { char[] ss = s.toCharArray(); int n = s.length(); boolean[][] dp = new boolean[n][n];// 创建dp表 int[] ret = new int[2];// 记录字符串的起始位置和结束位置 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] : true; if(dp[i][j] == true) { if(j - i > ret[1] - ret[0]) { ret[0] = i;ret[1] = j; } } } } return s.substring(ret[0],ret[1] + 1);// 注意是"左闭右开" } }
算法系列--动态规划--回文子串系列（下）https://developer.aliyun.com/article/1480806?spm=a2c6h.13148508.setting.26.361f4f0eyTL4lb
