博文中会简要介绍Leetcode P0005题目分析及解题思路。
“Longest Palindromic Substring”是一道非常经典的动态规划问题，题干如下：
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
基于动态规划的思想，我们知道这道题的核心思路在于找到最优子结构。那么如何找到最优子结构呢？首先思考的问题核心是一个回文子串的约束条件是什么，换言之就是如何确定一个回文子串。
一个回文串，首先两端字符必须相等，其次除去两端字符后的子串也要是一个回文子串。
仔细观察上述描述不难发现，其实回文串的定义是递归性质的，即一个回文串除去两端字符后也必须是个回文串。自然这样的定义也就引出了我们的最优子结构，即想要找到一个回文子串，需要满足如下约束，一是两端字符相等，二是除去两端字符后也是一个回文串。
找到最优子结构后，我们自然而然会去思考，如何用数学上的递推式来表达。一般来说看到“两端”这样的说法，首先要想到能否将一端固定，只增减另一端。如果可以，那么这是一个线性动态规划；如果不行，则是一个二维动态规划。显然，在这道题里，一个回文串是两端增长的，是一个二维动态规划。于是我们得到数学递推式：
dp[i][j] = dp[i+1][j-1]+2, if dp[i+1][j-1] > 0 && s[i] == s[j]
其中dp[i+1][j-1] > 0表示字符串i+1到j-1的子串是一个回文串，s[i] == s[j]则意味着两端字符相等。
以下是Java的题解代码实现。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0 || s.length() == 1)
return s;
int[][] dp = new int[s.length()][s.length()];
char[] chars = s.toCharArray();
int maxLen = 0;
String subStr = null;
for (int idx=0; idx<s.length(); ++idx) {
dp[idx][idx] = 1;
if (idx != s.length()-1 && chars[idx] == chars[idx+1]) {
dp[idx][idx+1] = 2;
if (maxLen == 0) {
maxLen = 2;
subStr = s.substring(idx, idx+2);
}
}
}
// DP
for (int i1=2; i1<chars.length; ++i1) {
for (int j2=i1-2; j2>=0; --j2) {
if (chars[i1] == chars[j2] && dp[j2+1][i1-1] > 0) {
dp[j2][i1] = dp[j2+1][i1-1] + 2;
}
if (dp[j2][i1] > maxLen) {
maxLen = dp[j2][i1];
subStr = s.substring(j2, i1+1);
}
}
}
return (maxLen != 0)? subStr: String.valueOf(chars[0]);
}
}
以下是C++的题解代码实现。
class Solution {
public:
string longestPalindrome(string s) {
if (s.length() <= 1)
return s;
int dp[1000][1000] = {0};
int max_len = 0;
string sub_str = s.substr(0, 1);
for (int idx=0; idx<s.length(); ++idx) {
dp[idx][idx] = 1;
if (idx != s.length()-1 && s[idx] == s[idx+1]) {
dp[idx][idx+1] = 2;
if (max_len == 0) {
max_len = 2;
sub_str = s.substr(idx, 2);
}
}
}
// DP
for (int i1=2; i1<s.length(); ++i1) {
for (int j2=i1-2; j2>=0; --j2) {
if (s[i1] == s[j2] && dp[j2+1][i1-1] > 0) {
dp[j2][i1] = dp[j2+1][i1-1] + 2;
}
if (max_len < dp[j2][i1]) {
max_len = dp[j2][i1];
sub_str = s.substr(j2, i1-j2+1);
}
}
}
return sub_str;
}
};