leetcode5

public class Solution {
private int lo, maxLen; public String LongestPalindrome(String s)
{
int len = s.Length;
if (len < )
return s; for (int i = ; i < len - ; i++)
{
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i + ); //assume even length.
}
return s.Substring(lo, maxLen);
} private void extendPalindrome(String s, int j, int k)
{
while (j >= && k < s.Length && s[j] == s[k])
{
j--;
k++;
}
if (maxLen < k - j - )
{
lo = j + ;
maxLen = k - j - ;
}
}
}

https://leetcode.com/problems/longest-palindromic-substring/#/description

补充一个python的实现,使用动态规划解决:

 class Solution:
def longestPalindrome(self, s: 'str') -> 'str':
n = len(s)
dp = [[False for _ in range(n)]for _ in range(n)]
count =
res = ''
for i in range(n):
dp[i][i] = True
if count < :
res = s[i]
count = for i in range(n-):
if s[i] == s[i+]:
dp[i][i+] = True
if count < :
res = s[i:i+]
count = for k in range(,n+):
for i in range(n-k+):
j = i + k -
if s[i] == s[j] and dp[i+][j-]:
dp[i][j] = True
if count < j + - i:
count = j + -i
res = s[i:j+]
return res
上一篇:怎么理解linux的平均负载及平均负载高后的排查工具


下一篇:手机客户端UI测试常见的测试点