动态规划之最长回文字符串(Java 版本)

题目描述：

回文字符串就是从前往后和从后往前读都一样的字符串。比如aabbaa,aaa,QoQ等等。现在给你一个字符串，你可以从中删去一些字符，在不改变原来字符相对顺序的情况下，得到一个最长回文字符串。

比如，abxdba,删去x,可以得到abdba,是一个回文字符串，你的任务就是求出给定的字符串删去若干字符后可以得到的最长回文字符串的长度。字符串长度不超过1000，字符范围从'a'到'z'。

输入：

多组输入，每组一行字符串。

输出：

每组输出一个整数，表示可以得到的最长的回文字符串的长度。

样例输入：

aabbaabb
computer
abzla
samhita

样例输出：

题目解析：

我们假设dp[i][j]为str[i,.....,j]的最长回文长度，那么如何找出规律呢？我们可以分情况进行讨论，当i=j时，dp[i][j]=1；当j=i+1时，如果str[i]=str[j],那么dp[i][j]=2,如果str[i]!=str[j],那么dp[i][j]=1;当j>=i+2时，我们可以用两层循环遍历搜索，第一层循环代表区间的长度（不超过str数组的长度），第二层循环代表区间的起始位置i，如果str[i]=str[j]，那么dp[i][j]=dp[i+1][j-1]+2;如果str[i]!=str[j]，那么dp[i][j]=max(dp[i+1][j],dp[i][j-1])。

参考代码：

import java.util.Scanner;

/**
 * 求最长回文子串
 * @author autumn_leaf
 * @Date 2019/03/23
 */
public class PalindSubstring {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			String s = sc.nextLine();
			//将一串字符转化为字符数组
			char[] str = s.toCharArray();
			int len = str.length;
			int[][] dp = new int[len+10][len+10];
			//dp数组初始化
			for(int i=0; i<len; i++) {
				dp[i][i] = 1;
			}
			//dp中相邻元素
			for(int i=0; i<len-1; i++) {
				if(str[i] == str[i+1]) {
					dp[i][i+1] = 2;
				}else {
					dp[i][i+1] = 1;
				}
			}
			/**dp中至少相隔一个元素*/
			/**k代表相隔的区间长度*/
			for(int k=2; k<len; k++) {
				//i代表区间起始位置
				for(int i=0; i+k<len; i++) {
					//j代表区间末尾位置
					int j = i+k;
					if(str[i] == str[j]) {
						dp[i][j] = dp[i+1][j-1] + 2;
					}else {
						dp[i][j] =Math.max(dp[i+1][j], dp[i][j-1]);
					}
				}
			}
			System.out.println(dp[0][len-1]);
		}
	}

}

下面以字符串abzla为例，画图表说明动态规划方程的正确性，其中i代表列，j代表行，表格内的值即为dp[i][j]的值。

i/j	0	1	2	3	4
0	1	1	1	1	1+2=3
1		1	1	1	1
2			1	1	1
3				1	1
4					1

运行截图如下：

动态规划之最长回文字符串(Java 版本)

好了，本题讲解结束，还有疑惑的同学可以在下方评论区留言哦！

动态规划之最长回文字符串(Java 版本)

相关推荐