Lintcode200 Longest Palindromic Substring solution 题解
发布在LINTCODE2018年2月5日view:373移动开发
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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); 【参考答案】

www.jiuzhang.com/solutions/longest-palindromic-substring/

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN

我的收藏