leetcode刷题记录（一百一十六）——5. 最长回文子串

（一）问题描述

5. 最长回文子串 - 力扣（LeetCode）5. 最长回文子串 - 给你一个字符串 s，找到 s 中最长的 回文 子串。 示例 1：输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。示例 2：输入：s = "cbbd"输出："bb" 提示： * 1 <= s.length <= 1000 * s 仅由数字和英文字母组成https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

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

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

 （二）解决思路

        这道题是用动态规划来解决的（乍一看很难想到动态规划上，但我觉得“最长”这种字眼出现了，在想不到其他方法的前提下都可以考虑是不是贪心或者动态规划）。

        dp数组是布尔型数组，dp[i][j]用来表示 i 和 j 之间的子串是不是回文串。

        比较容易看出的递推关系是，对于任何满足s.charAt(i)=s.charAt(j)的子串，dp[i][j]=dp[i+1][j-1]，例如在abba这个回文串里dp[0][3]=dp[1][2]。这里要比较哪个回文子串的长度更长，所以比较特别的一点是遍历的是子串的长度，而非终止位置j，j是通过子串长度和起始位置i计算得到的。

class Solution {public String longestPalindrome(String s) {int m = s.length();if(m<2) return s;boolean[][] dp = new boolean[m][m];for(int i=0;i<m;i++){dp[i][i]=true;}//begin用来记录最长回文子串的起始位置int begin=0;int maxLen=1;//遍历长度，用长度和起始位置i来计算终止位置jfor(int len=2;len<=m;len++){for(int i=0;i<m;i++){int j = len+i-1;if(j>=m) break;if(s.charAt(i)!=s.charAt(j)){dp[i][j]=false;}else{if(j-i<2){dp[i][j]=true;}else{//当j-i<2时，这种情况会导致j-1<i+1，此时dp[i+1][j-1]不合法；//boolean默认值为falsedp[i][j] = dp[i+1][j-1];}  }if(dp[i][j]&&j-i+1>maxLen){maxLen = j-i+1;begin = i;}}}return s.substring(begin,begin+maxLen);}
}