5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
给定一个字符串s，返回最长回文子串。
概念解析
在解决这道问题之前，我们需要先了解一下最长回文子串的概念。
回文子串：是指一个长度为n的字符串S，其中s[i] = s[n-i-1]，即字符串的前半段和后半段基于”中间线“对称。
最长回文子串：即在一个字符串中最长的回文子串。
题目思考
class Solution:
def longestPalindrome(self, s: str) -> str:
def check_palindromic(s: str) -> bool:
ret = True
s_len = len(s)
s_len2 = s_len - 1
for i in range(int(s_len/2)):
if s[i] == s[s_len2 - i]:
continue
else:
ret = False
break
return ret
max_p = 1
s_len = len(s)
# _arr = [0]*s_len
ret_arr = s[0]
for i in range(s_len - 1):
# if _arr[i] ==0:
k = i
# _arr[i] = 0
while 1:
if s[i] not in s[k+1:]:
break
j = s.index(s[k], k+1)
# _arr[j] = 1
if check_palindromic(s[i:j+1]):
if (j-i+1) > max_p:
max_p = j-i+1
ret_arr = s[i:j+1]
k = j
return ret_arr
我的方法也算是一种暴力破解法：从头开始遍历字符串，从字符串中找到下一个和当前遍历的字符一样的字符。然后比较这两个字符之间是否属于回文。然后再继续寻找下一个相同字符，并判断是否属于回文。比较并记录最大值。我默认了长度是1，最初回文就第一个字符。我以为我这个暴力破解很完美了。但是。。。还是有但是。。。
当我遇到以下情况的时候。。。
"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
当出现这种情况的时候就很明显会超时了。果断放弃。看一看解析和别人的讨论。
答案解析
我的天，答案居然给了五种方案，那只能慢慢解析了。
1.Longest Common Substring 最长公共子串
通过将字符串反转，比较并找出原字符串和反转字符串之间的最长公共子串。
例如S = "caba" S' = "abac". 这两个字符串之间的最长公共子串是‘aba’。
class Solution {
public:
string longest_common_substring(string str1, string str2)
{
int s1 = str1.size(); int s2 = str2.size();
int dp[s1+1][s2+1];
string res ; int max = 0 ;
for(int i=0; i<=s1; i++)
{
for(int j=0; j<=s2; j++)
{ if(i==0 || j==0){ dp[i][j] = 0;}
else if(str1[i-1] == str2[j-1])
{
dp[i][j] = 1 + dp[i-1][j-1];
if(dp[i][j]>max)
{
string temp = str1.substr(i-dp[i][j], dp[i][j]) ;
string revtemp = string(temp.rbegin(),temp.rend());
if(revtemp==temp)
{
max = dp[i][j] ;
res = temp ;
}
}
}
else
{ dp[i][j] = 0 ; }
}
}
return res;
}
string longestPalindrome(string s)
{
string srev = string(s.rbegin(),s.rend());
return longest_common_substring(s, srev);
}
};
这个方法我是从讨论区摘抄的。我个人在参考了维基百科上面的内容之后并没有写出函数，应该是我理解的不到位。我们稍微的解析一下别人的代码。
代码在一开始的时候创建了一个行数为第一个字符串长度，列数为第二个字符串长度的二维数组（行代表第一个字符串的每一位字符，列代表第二个字符串的每一位字符。需要注意的是在这时候的二维数组里面每一个斜线分别对应着一种偏差的可能性，这也是为什么要多一个0行/列的原因。）。遍历字符串，修改二维数组里面的数值，当遇到字符串相同的情况，就将数值设置为左上方元素+1。比较并记录这个最大值（可以通过当前位置的数值，来判断需要往前几位）。
但是这种比较方法有一点需要注意的是：
S = "abacdfgdcaba", S′ = "abacdgfdcaba"。在这种情况下，当字符串内出现非回文子串的对称字符串，单纯的比较字符串中间是否相等就会出错。所以可以在这之后加上索引比较。所以在后面再对已知字符串进行判断是否属于回文。
2.Brute Force 暴力破解
这个方法最暴利，从头遍历字符串，字符串挨个字符往前找，然后判断是否属于回文。比较并记录最大值。和我写的很像，但是由于会超时，所以无法用在这里，
3.Dynamic Programming 动态规划
循环遍历每个字符，把这个字符作为回文里面的中间节点。
P(i, i) = true
P(i, i+1) = ( S_i == S_{i+1} )
将节点本身看作为一位的回文。然后开始扩展，找到最大的回文。
#python3 Space : O(n)
def longestPalindrome(self, s: str) -> str:
if not s: return s
n, l, r = len(s), 0, 0
dp = [[True]*n, [False]*n] # dp[0]: old letters palindromes, dp[1]: even letters palindromes
for i in range(n-1):
if s[i] == s[i+1]:
dp[1][i] = True
l, r = i, i+1
for m in range(2, n): # m letters palindromes
for i in range(n-m):
j = i+m
x, k = m%2, i+m//2
dp[x][k] = dp[x][k] and s[i] == s[j]
if dp[x][k] and j-i > r-l:
l, r = i, j
return s[l:r+1]
#python3 Space: O(n^2)
def longestPalindrome(self, s: str) -> str:
if not s: return s
n, l, r = len(s), 0, 0
dp = [[False]*n for _ in range(n)]
dp[-1][-1] = True
for i in range(n-1):
dp[i][i] = True
if s[i] == s[i+1]:
dp[i][i+1] = True
l, r = i, i+1
for m in range(2, n):
for i in range(n-m):
j = i+m
dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
if dp[i][j] and j-i > r-l:
l, r = i, j
return s[l:r+1]
4.Expand Around Center 中心展开
#java
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
#python3
def longestPalindrome(self, s: str) -> str:
def check(l, r):
while 0 <= l and r < n and s[l] == s[r]:
l -= 1
r += 1
return l, r
n, L, R = len(s), 0, 0
for i in range(2*n-1):
if i%2: l, r = check((i-1)//2, (i+1)//2)
else: l, r = check(i//2, i//2)
if r-l > R-L: L, R = l, r
return s[L+1:R]
#python3
#将字符串里面插入特殊字符，把所有的都可以当作奇数来进行扩展
def longestPalindrome(self, s: str) -> str:
t = '^#'+'#'.join(s)+'#$'
c = r = 0 # center and radius
for i in range(1,len(t)-1):
j = 1 if t[i] == '#' else 2 # skip '#' and check letters only
while t[i-j] == t[i+j]: j += 2
if j > r: c, r = i, j
return s[(c-r+1)//2:(c+r-1)//2]
遍历字符串每个字符，然后根据不同的奇数位或者偶数位的情况向外扩展，找到回文，记录并比较最大值。
5.Manacher's Algorithm
def longestPalindrome(self, s: str) -> str:
t = '^#'+'#'.join(s)+'#$'
n = len(t)
p = [0]*n
c = r = cm = rm = 0
for i in range (1, n-1):
p[i] = min(r-i, p[2*c-i]) if r > i else 0
while t[i-p[i]-1] == t[i+p[i]+1]: p[i] += 1
if p[i]+i > r: c, r = i, p[i]+i
if p[i] > rm: cm, rm = i, p[i]
return s[(cm-rm)//2:(cm+rm)//2]
回文子串又可以分为奇长度回文子串，偶长度回文子串。为了简化问题，我们可以在字符中间加上一个特殊符号如‘c
a
b
”，从而将偶长度回文子串变成奇长度回文子串。
总结
总的来看这道题不算很难。但是题目解题思路多变，实话说这题我看了两天才看明白。。。
