【题目描述】
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of Sis 1000, and there exists one unique longest palindromic substring.
给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。
【题目链接】
www.lintcode.com/en/problem/longest-palindromic-substring/
【题目解析】
此题可使用区间类动态规划。
用dp[i][j]来存DP的状态，需要较多的额外空间: Space O(n^2)
DP的4个要素
状态：
dp[i][j]: s.charAt(i)到s.charAt(j)是否构成一个Palindrome
转移方程：
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
初始化：
dp[i][j] = true when j - i <= 2
结果：
找maxLen = j - i + 1;，并得到相应longest substring：longest = s.substring(i, j + 1);
【参考答案】
网友评论