回文串是从左到右和从右到左读起来一样的字符串,变种还有回文子序列,区别就是字符可以不连续。
求回文串个数、最长回文串、最长回文序列也是典型的二维动态规划问题。
我们通过几个简单的案例看一下这些题目的规律。
案例1:给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
首先我们要明白:
①单个字符串肯定是回文串,
②两个字符,如果相同也是回文串
③超过三个字符序列的情况,如果最前最后两个字符相同,回文序列的长度就可以在去掉最前最后两个字符的回文序列+2
④如果最前最后两个字符串不相同,我们只好退其次,求解dp[i +1][j], dp[i][j - 1]两个的较大值
我们定义dp[i][j]为字符串中从i到j的最长回文子序列的长度,显而易见,dp[i][i]是回文的。
当s[i]==s[j]时,有dp[i][j] = dp[i + 1][j - 1] + 2
当s[i]!=s[j]时,有dp[i][j] = max{dp[i +1][j], dp[i][j - 1]}
我们要求的最终值就是dp[0][n-1]
为了保证求解当前问题是所有子问题已经求解,需要考虑遍历的顺序。
首先:因为i<=j,所有我们只需要求解上三角矩阵的值即可。
i,j-1 | i,j | |
i+1,j |
注意观察dp[i][j]的子问题,一个在自己的下方格子,一个在自己的左边格子,
也就是说我们的每一行的遍历要从下到上,每一列的遍历要从左到右。
public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int i = n - 1; i >= 0; i--) { //单个字符是回文的,长度为1 dp[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i +1][j], dp[i][j - 1]); } } } return dp[0][n - 1]; }
案例2:给你一个字符串 s
,请你统计并返回这个字符串中 回文子串 的数目。
这个题目要求回文串,跟上一题目是有区别的,回文串必须是连续的。
遍历顺序还是一样行从下到上,列从左到有。
回文串要求最前最后两个字符必须相同,且取掉最前最后两个字符的子串仍然是回文串
public int countSubstrings(String s) { int n = s.length(); boolean[][] dp = new boolean[n][n]; int ans = 0; for (int i = n-1; i >=0; i--) { for (int j = i; j < n; j++) {//j-i==0,单字符是回文串,j-i=1两个字符相等也是回文串 if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) { dp[i][j] = true; ans++; } } } return ans; }
留一个未解题目
案例3(5):给你一个字符串 s
,找到 s
中最长的回文子串。