广告传媒公司招聘信息_北京王府井附近景点攻略_市场营销毕业后做什么工作_百度一下就知道百度首页

https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked

5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

1. 状态定义
   我们用一个二维数组 dp[i][j] 表示子串 s[i…j] 是否是回文：

dp[i][j] = true 表示子串 s[i…j] 是回文；
dp[i][j] = false 表示子串 s[i…j] 不是回文。
2. 状态转移方程
要判断子串 s[i…j] 是否是回文，需要满足以下两个条件：

两端字符相等：s[i] == s[j]
内部子串 s[i+1…j-1] 也是回文：dp[i+1][j-1] = true
因此状态转移方程为：

dp[i][j]=(s[i]==s[j]) && (j−i<2 ∣∣ dp[i+1][j−1])
如果子串长度为 1（j - i == 0），它本身是回文。
如果子串长度为 2（j - i == 1），只需判断 s[i] == s[j]。
如果子串长度大于 2（j - i > 1），还需要判断 dp[i+1][j-1] 是否为 true。

这题去遍历各种子串的循环有点意思。外层是字符串长度从1到n。内层是子串的起始位置。子串的结束位置j是i和len算出来的。

class Solution {public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];int maxLen = 1;int start = 0;for(int len = 1;len<=n;len++){for(int i=0;i<=n-len;i++){int j = i+len-1;if(s.charAt(i)==s.charAt(j)){if(len<=2){dp[i][j]=true;} else{dp[i][j]=dp[i+1][j-1];}}if(dp[i][j] && len>maxLen){maxLen = len;start = i;}}}return s.substring(start,start+maxLen);}
}