[LeetCode] 5. 最长回文子串

题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

题目描述:

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例:

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

思路:

三种思路:

  1. 把每个字母当成回文串的中心

    这里要考虑两种情况,回文串的长度为奇数或者偶数情况.

  2. 把每个字母当成回文串的结束

  3. dp[i][j]表示字符串从ji是否是为回文串,即当s[j] == s[i]如果dp[i-1][j+1]也是回文串,那么字符串从ji也是回文串,即dp[i][j]为真

代码:

方法一:

class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
self.res = ""
def helper(i,j):
while i >= 0 and j < n and s[i] == s[j]:
i -= 1
j += 1
if len(self.res) < j - i -1 :
self.res = s[i+1:j]
for i in range(n):
helper(i,i)
helper(i,i+1)
return self.res

方法二

class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
max_len = 1
n = len(s)
start = 0
for i in range(1,n):
even = s[i-max_len:i+1]
odd = s[i - max_len-1:i+1]
#print(even,odd)
if i - max_len - 1 >= 0 and odd == odd[::-1]:
start = i - max_len - 1
max_len += 2
elif i - max_len >=0 and even == even[::-1]:
start = i - max_len
max_len += 1 #print(start,max_len)
return s[start: start+max_len]

方法3

class Solution:
def longestPalindrome(self, s: str) -> str:
if not s :
return ""
res = ""
n = len(s)
dp = [[0] * n for _ in range(n)]
max_len = float("-inf")
#print(dp)
for i in range(n):
for j in range(i,-1,-1):
if s[i] == s[j] and (i - j < 2 or dp[i-1][j+1]):
dp[i][j] = 1
if dp[i][j] and max_len < i - j + 1:
#print("i,j",i,j)
res = s[j:i+1]
max_len = i - j + 1
return res

java

class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
boolean[][] dp = new boolean[n][n];
for(int i = 0 ;i < n; i++){
for(int j = i; j >= 0 ;j --){
if(s.charAt(i) == s.charAt(j) && ( i - j < 2 || dp[i-1][j+1]))
dp[i][j] = true;
if (dp[i][j] && (i - j + 1 > res.length())){
res = s.substring(j,i+1);
}
}
}
return res; }
}
上一篇:Java Annotation 及几个常用开源项目注解原理简析


下一篇:Android 启动过程简析