【Leetcode 5】最长回文字串 —— 动态规划

5. 最长回文字串

给你一个字符串s，找到s中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：“bb”

题目分析

经典动态规划问题，更多案例可见 Leetcode 动态规划详解

我们可以使用动态规划解决本题，解题思路：

1. 状态定义：dp[l][r]表示起点为i，终点为j的字串是否回文串
2. 状态转移方程：dp[l][r] = dp[l + 1][r - 1] && char[l] == char[r]，即dp[l + 1][r - 1]为回文串且i和j的字符相同

动态规划一般用于求解具有重叠子问题和最优子结构的问题，例如最长公共子序列、背包问题、最短路径等。重叠子问题指的是在求解问题的过程中，多次用到相同的子问题，最优子结构指的是问题的最优解可以通过子问题的最优解来构造

class Solution {
	/**
	 * 状态转移方程：dp[l][r] = dp[l + 1][r - 1] && char[l] == char[r]
	 * @param s
	 * @return
	 */
	public String longestPalindrome(String s) {
		if (s == null || s.length() < 2) {
			return s;
		}
		int n = s.length();
		//最长回文串的起点、终点和长度
		int maxStart = 0, maxEnd = 0, maxLen = 1;
		boolean[][] dp = new boolean[n][n];
		for (int r = 1; r < n; r++) {
			for (int l = 0; l < r; l++) {
				if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
					dp[l][r] = true;
					if (r - l + 1 > maxLen) {
						maxLen = r - l + 1;
						maxStart = l;
						maxEnd = r;
					}
				}
			}
		}
		return s.substring(maxStart, maxEnd + 1);
	}
}