# [LeetCode] Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

# 实现代码

const int LEN = 1001;
int c[LEN][LEN];
class Solution {
public:
string longestPalindrome(string s)
{
memset(c, 0, sizeof(c));
string s2 = "";
int i = s.size() - 1;
while (i >= 0)
{
s2 += s[i--];
}
int maxLen = 0;
int maxI = 0;
for (i = 1; i <= s.size(); i++)
{
for (int j = 1; j <= s2.size(); j++)
{
if (s[i-1] == s2[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
if (c[i][j] > maxLen)
{
maxLen = c[i][j];
maxI = i - 1;
}
}
}
}

return s.substr(maxI - maxLen + 1, maxLen);
}
};

// Runtime: 260 ms
const int LEN = 1000;
bool c[LEN][LEN];
class Solution {
public:
string longestPalindrome(string s)
{
memset(c, 0, sizeof(c));
int maxLen = 0;
string temp;
for (int i = s.size() - 1; i >= 0; i--)
{
for (int j = i; j < s.size(); j++)
{
if (s[i] == s[j] && (j - i <= 2 || c[i+1][j-1]))
{
c[i][j] = true;
if (j - i + 1 > maxLen)
{
maxLen = j - i + 1;
temp = s.substr(i, j - i + 1);
}
}
}
}

return temp;
}
};

Java:

// Runtime: 460 ms
public class Solution {
public String longestPalindrome(String s) {
boolean b[][] = new boolean[s.length()][s.length()];
int maxLen = 0;
String temp = "";
for (int i = s.length() - 1; i >= 0; i--){
for (int j = i; j < s.length(); j++){
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || b[i+1][j-1])){
b[i][j] = true;
if (j - i + 1 > maxLen){
maxLen = j - i + 1;
temp = s.substring(i, j + 1);
}
}
}
}

return temp;
}
}

Python版本如下，但是写出来超时了，暂时没有找到其他好办法，请各位指教。

class Solution:
# @param {string} s
# @return {string}
def longestPalindrome(self, s):
b = [[False] * len(s) for i in range(len(s))]
result = ''
maxLen = 0
for i in range(len(s), 0, -1):
for j in range(i, len(s)):
if s[i] == s[j] and (j - i <= 2 or b[i+1][j-1]):
b[i][j] = True
if j - i + 1 > maxLen:
maxLen = j - i + 1
result = s[i:j+1]

return result

+ 订阅