LeetCode：最长回文子串【5】

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

题目分析

　　1.一个常见的错误！

　　　　有些人会忍不住提出一个快速的解决方案，不幸的是，这个解决方案有缺陷(但是可以很容易地纠正)：

反转 SS，使之变成 S'S′。找到 SS 和 S'S′ 之间最长的公共子串，这也必然是最长的回文子串。

　　这似乎是可行的，让我们看看下面的一些例子。例如，S=“caba” , S′=“abac”：SS 以及 S'S′ 之间的最长公共子串为“aba”，恰恰是答案。

　　让我们尝试一下这个例子：S=“abacdfgdcaba” , S′=“abacdgfdcaba”：SS 以及 S'S′ 之间的最长公共子串为“abacd”，显然，这不是回文。

　　2.动态规划的思路！

　　为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑“ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

　　我们给出P(i,j)的定义如下：

　　

　　因此有，

　　

　　这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…

Java题解

class Solution { public String longestPalindrome(String s) { if(s==null||s.length()==0) return s; String res =""; boolean [][] dp = new boolean[s.length()][s.length()]; int max = 0; for(int j=0;j<s.length();j++) { for(int i=0;i<=j;i++) { if(i==j||((j==i+1)&&s.charAt(i)==s.charAt(j))) dp[i][j]=true; else dp[i][j]=(s.charAt(i)==s.charAt(j))&&(dp[i+1][j-1]); if(dp[i][j]&&j-i+1>max) { max=j-i+1; res = s.substring(i,j+1); } } } return res; } }

　　

 

转载于:https://www.cnblogs.com/MrSaver/p/9716461.html