最长回文子串 中等🌟🌟🌟🌟🌟
问题描述
原文链接：5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
代码实现
Java
class Solution {
/* 动态规划三部曲
s = "cba"
1、
dp[i][j]：字符串[i...j]是否为回文串=》长度：j - i + 1
2、关系式
s[i] == s[j]=>dp[i][j] = dp[i+1][j-1]=>
s[i] != s[j] =>dp[i][j] false。
3、初始值
dp[0..i][0] = true.
*/
public String longestPalindrome(String s) {
char[] c = s.toCharArray();
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0;
int end = 0;
int max = 0;
for(int i = 0; i < n; i++){
dp[i][0] = true;
}
for(int j = 1; j < n; j++){
for(int i = 0; i < j; i++){
if(c[i] != c[j]){
dp[i][j] = false;
}else{
if(j - i + 1 > 3){
dp[i][j] = dp[i+1][j-1];
}else{
dp[i][j] = true;
}
}
if(dp[i][j] && j - i + 1 > max){
max = j - i + 1;
start = i;
end = j;
}
}
}
return s.substring(start, end + 1);
}
}
Python
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# 动态规划三部曲
# s = "cba"
# 1、
# dp[i][j]：字符串[i...j]是否为回文串=》长度：j - i + 1
# 2、关系式
# s[i] == s[j]=>dp[i][j] = dp[i+1][j-1]=>
# s[i] != s[j] =>dp[i][j] false。
# 3、初始值
# dp[0..i][0] = true.
c = list(s)
n = len(s)
dp = [[False] * n for _ in range(n)]
start = 0
end = 0
max_len = 0
for i in range(n):
dp[i][0] = True
for j in range(1, n):
for i in range(j):
if c[i] != c[j]:
dp[i][j] = False
else:
if j - i + 1 > 3:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = True
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
start = i
end = j
return s[start:end+1]
C++
class Solution {
public:
string longestPalindrome(string s) {
/*
动态规划三部曲
s = "cba"
1、
dp[i][j]：字符串[i...j]是否为回文串=》长度：j - i + 1
2、关系式
s[i] == s[j]=>dp[i][j] = dp[i+1][j-1]=>
s[i] != s[j] =>dp[i][j] false。
3、初始值
dp[0..i][0] = true.
*/
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0;
int end = 0;
int max_len = 0;
for(int i = 0; i < n; i++) {
dp[i][0] = true;
}
for(int j = 1; j < n; j++) {
for(int i = 0; i < j; i++) {
if(s[i] != s[j]) {
dp[i][j] = false;
} else {
if(j - i + 1 > 3) {
dp[i][j] = dp[i+1][j-1];
} else {
dp[i][j] = true;
}
}
if(dp[i][j] && j - i + 1 > max_len) {
max_len = j - i + 1;
start = i;
end = j;
}
}
}
return s.substr(start, end - start + 1);
}
};
Go
func longestPalindrome(s string) string {
/*
动态规划三部曲
s = "cba"
1、
dp[i][j]：字符串[i...j]是否为回文串=》长度：j - i + 1
2、关系式
s[i] == s[j]=>dp[i][j] = dp[i+1][j-1]=>
s[i] != s[j] =>dp[i][j] false。
3、初始值
dp[0..i][0] = true.
*/
n := len(s)
dp := make([][]bool, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
dp[i][0] = true
}
start := 0
end := 0
maxLen := 0
for j := 1; j < n; j++ {
for i := 0; i < j; i++ {
if s[i] != s[j] {
dp[i][j] = false
} else {
if j - i + 1 > 3 {
dp[i][j] = dp[i+1][j-1]
} else {
dp[i][j] = true
}
}
if dp[i][j] && j - i + 1 > maxLen {
maxLen = j - i + 1
start = i
end = j
}
}
}
return s[start:end+1]
}