算法leetcode
给你一个字符串 s，找到 s 中最长的回文子串。
代码语言：javascript复制示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法
代码语言：javascript复制class Solution {
public String longestPalindrome(String s) {
boolean dp[][] = new boolean[s.length()][s.length()];
for(int i = 0;i < dp.length;i ){
for(int j =0 ;j<dp[i].length;j ){
dp[i][j] = false;
}
}
int ans = 1;
Map<Integer, String> map = new HashMap<>();
for(int m = dp.length-1 ; m>=0 ; m--){
for(int n = m ;n<dp.length;n ){
if(s.charAt(m) == s.charAt(n)){
if(n-m<1){
dp[m][n]=true;
//计算出长度最长的回文串
ans = Math.max(ans, n-m 1);
map.put(1, s.substring(m,n 1));
}else if(n-m==1){
dp[m][n]=true;
ans = Math.max(ans, n-m 1);
map.put(2, s.substring(m,n 1));
//如果m n条件满足、执行以下语句
}else if(dp[m 1][n-1]){
ans = Math.max(ans, n-m 1);
dp[m][n]=true;
map.put(n-m 1, s.substring(m,n 1));
}
}
}
}
System.out.println(map);
return map.get(ans);
}
}本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处 最后编辑时间为: 2021/12/05 12:06
