一、题目
所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如 “a”、“aba”、“abba”。
对于一个字符串,其子串是指连续的一段子字符串,而子序列是可以非连续的一段子字符串。
最长回文子串和最长回文子序列(Longest Palindromic Subsequence)是指任意一个字符串,它说包含的长度最长的回文子串和回文子序列。
例如:字符串 “ABCDDCEFA”,它的最长回文子串即 “CDDC”,最长回文子序列即 “ACDDCA”。
二、最长回文子串
1. 思路
首先这类问题通过穷举的办法,判断是否是回文子串并再筛选出最长的,效率是很差的。我们使用动态规划的策略来求解它。首先我们从子问题入手,并将子问题的解保存起来,然后在求解后面的问题时,反复的利用子问题的解,可以极大的提示效率。
由于最长回文子串是要求连续的,所以我们可以假设j
为子串的起始坐标,i
为子串的终点坐标,其中i
和j
都是大于等于0
并且小于字符串长度length
的,且j <= i
,这样子串的长度就可以使用i - j + 1
表示了。
我们从长度为 1 的子串依次遍历,长度为 1 的子串肯定是回文的,其长度就是 1;然后是长度为 2 的子串依次遍历,只要str[i]
等于str[j]
,它就是回文的,其长度为 2;接下来就好办了,长度大于 2 的子串,如果它要满足是回文子串的性质,就必须有str[i]
等于str[j]
,并且去掉两头的子串str[j+1 ... i-1]
也一定是回文子串,所以我们使用一个数组来保存以j
为子串起始坐标,i
为子串终点坐标的子串是否是回文的,由于我们是从子问题依次增大求解的,所以求解[i ... j]
的问题时,比它规模更小的问题结果都是可以直接使用的了。
2. 代码
public class Main {public static void main(String[] args) {String s = "cabbaeeaf";System.out.println(getLPS(s));}public static String getLPS(String s) {char[] chars = s.toCharArray();int length = chars.length;// 第一维参数表示起始位置坐标,第二维参数表示终点坐标// lps[j][i] 表示以 j 为起始坐标,i 为终点坐标是否为回文子串boolean[][] lps = new boolean[length][length];int maxLen = 1; // 记录最长回文子串最长长度int start = 0; // 记录最长回文子串起始位置for (int i = 0; i < length; i++) {for (int j = 0; j <= i; j++) {if (i - j < 2) {// 子字符串长度小于 2 的时候单独处理lps[j][i] = chars[i] == chars[j];} else {// 如果 [i, j] 是回文子串,那么一定有 [j+1, i-1] 也是回子串lps[j][i] = lps[j + 1][i - 1] && (chars[i] == chars[j]);}if (lps[j][i] && (i - j + 1) > maxLen) {// 如果 [i, j] 是回文子串,并且长度大于 max,则刷新最长回文子串maxLen = i - j + 1;start = j;}}}return s.substring(start, start + maxLen);}}
三、最长回文子序列
1. 思路
子序列的问题将比子串更复杂,因为它是可以不连续的,这样如果穷举的话,问题规模将会变得非常大,我们依旧是选择使用动态规划来解决。
首先我们假设str[0 ... n-1]
是给定的长度为 n 的字符串,我们使用lps(0, n-1)
表示以 0 为起始坐标,长度为 n-1 的最长回文子序列的长度。那么我们需要从子问题开始入手,即我们一次遍历长度 1 到 n-1 的子串,并将子串包含的最长回文子序列的长度保存在 lps 的二维数组中。
遍历过程中,回文子序列的长度一定有如下性质:
如果子串的第一个元素str[j]
和最后一个元素str[i+j]
相等,那么lps[j, i+j] = lps[j+1, i+j-1] + 2
,其中lps[j+1, i+j-1]
表示去掉两头元素的最长子序列长度。如果两端的元素不相等,那么lps[j, i+j] = max(lps[j][i+j-1], lps[j+1][i+j])
,这两个表示的分别是去掉末端元素的子串和去掉起始元素的子串。
2. 代码
public class Main {public static void main(String[] args) {String s = "cabbeaf";System.out.println(getLPS(s));}public static int getLPS(String s) {char[] chars = s.toCharArray();int length = chars.length;// 第一维参数表示起始位置的坐标,第二维参数表示长度,使用 0 表示长度 1int[][] lps = new int[length][length];for (int i = 0; i < length; i++) {lps[i][i] = 1; // 单个字符的最长回文子序列长度为1,特殊对待一下}// (i + 1) 表示当前循环的子字符串长度for (int i = 1; i < length; i++) {// j 表示当前循环的字符串起始坐标for (int j = 0; i + j < length; j++) {// 即当前循环的子字符串坐标为 [j, i + j]// 所以第一个字符是 chars[j],最后一个字符就是 chars[i + j]if (chars[j] == chars[i + j]) {lps[j][i + j] = lps[j + 1][i + j - 1] + 2;} else {lps[j][i + j] = Math.max(lps[j][i + j - 1], lps[j + 1][i + j]);}}}// 最大值一定在以0为起始点,长度为 length - 1 的位置return lps[0][length - 1];}}
最后,这题只返回了最长回文子序列的长度,一般面试题中也只是要求返回长度即可。但是如果你也想知道最长回文子序列具体是啥,这可以额外添加一个变量记录最长回文子序列是哪些字符,例如维护一个键为lps[j][i + j]
,值为String
的 map。
如果觉得《动态规划:最长回文子串 最长回文子序列》对你有帮助,请点赞、收藏,并留下你的观点哦!