代码拉取完成,页面将自动刷新
同步操作将从 光花梗虎耳草/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个字符串 s
,找到 s
中最长的回文子串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
示例 3:
输入:s = "a" 输出:"a"
示例 4:
输入:s = "ac" 输出:"a"
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母(大写和/或小写)组成动态规划法。
设 dp[i][j]
表示字符串 s[i..j]
是否为回文串。
j - i < 2
,即字符串长度为 2 时,只要 s[i] == s[j]
,dp[i][j]
就为 true。j - i >= 2
,dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]
。class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
start, mx = 0, 1
for j in range(n):
for i in range(j + 1):
if j - i < 2:
dp[i][j] = s[i] == s[j]
else:
dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
if dp[i][j] and mx < j - i + 1:
start, mx = i, j - i + 1
return s[start:start + mx]
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int mx = 1, start = 0;
for (int j = 0; j < n; ++j) {
for (int i = 0; i <= j; ++i) {
if (j - i < 2) {
dp[i][j] = s.charAt(i) == s.charAt(j);
} else {
dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
if (dp[i][j] && mx < j - i + 1) {
mx = j - i + 1;
start = i;
}
}
}
return s.substring(start, start + mx);
}
}
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0, mx = 1;
for (int j = 0; j < n; ++j) {
for (int i = 0; i <= j; ++i) {
if (j - i < 2) {
dp[i][j] = s[i] == s[j];
} else {
dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
}
if (dp[i][j] && mx < j - i + 1) {
start = i;
mx = j - i + 1;
}
}
}
return s.substr(start, mx);
}
};
func longestPalindrome(s string) string {
n := len(s)
dp := make([][]bool, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
}
mx, start := 1, 0
for j := 0; j < n; j++ {
for i := 0; i <= j; i++ {
if j-i < 2 {
dp[i][j] = s[i] == s[j]
} else {
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
}
if dp[i][j] && mx < j-i+1 {
mx, start = j-i+1, i
}
}
}
return s[start : start+mx]
}
public class Solution{
public string LongestPalindrome(string s) {
int n = s.Length;
bool[,] dp = new bool[n, n];
int mx = 1, start = 0;
for (int j = 0; j < n; ++j)
{
for (int i = 0; i <= j; ++i)
{
if (j - i < 2)
{
dp[i, j] = s[i] == s[j];
}
else
{
dp[i, j] = dp[i + 1, j - 1] && s[i] == s[j];
}
if (dp[i, j] && mx < j - i + 1)
{
mx = j - i + 1;
start = i;
}
}
}
return s.Substring(start, mx);
}
}
import std/sequtils
proc longestPalindrome(s: string): string =
let n: int = s.len()
var
dp = newSeqWith[bool](n, newSeqWith[bool](n, false))
start: int = 0
mx: int = 1
for j in 0 ..< n:
for i in 0 .. j:
if j - i < 2:
dp[i][j] = s[i] == s[j]
else:
dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]
if dp[i][j] and mx < j - i + 1:
start = i
mx = j - i + 1
result = s[start ..< start+mx]
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。