5. 最长回文子串
class Solution:
def longestPalindrome(self, s: str) -> str:
'''
中心扩展法：O(n^2), O(1), 2*n-1个中心点，相当于在s中每两个字符之间插入一个位置， 每次center遍历到这个 "插入的位置"，中心扩散的中心left和right就分别指向两个
'''
res = ''
n = len(s)
for center in range(2*n-1):
left = center//2
right = left + center%2 # 和left指向同一个或者往前指向连续的下一个
while left >= 0 and right < n and s[left] == s[right]:
tmp = s[left:right+1]
tmp_len = len(tmp)
if tmp_len > len(res):
res = tmp
left-=1
right+=1
return res
'''动态规划： O(n^2), O(n^2)'''
res = ''
n = len(s)
dp = [[False]*n for _ in range(n)]
for j in range(n):
for i in range(j+1): #i在j的前面
if s[i] == s[j] and (j-i<2 or dp[i+1][j-1]):
dp[i][j] = True
if j-i+1 > len(res):
res = s[i:j+1]
return res
### 关键是需要利用dp数组辅助得到 start_index和max_len
if(not s or len(s)==1):
return s
n=len(s)
dp=[[False]*n for _ in range(n)] #实际上一个下三角矩阵就行(对称), dp[i][j]表示s[i:j]是否为回文串
start, max_len = 0, 1 #初始化最长回文子串的开始索引start， 最长长度max_len=1
for i in range(n):
dp[i][i]=True #所有单个字符都是回文串
if(i<n-1 and s[i]==s[i+1]): #若两相邻的字符相同，则将这两个字符对应的位置的dp都置为True
dp[i][i+1]=True
start, max_len = i, 2
for l in range(3,n+1): #回文子串的长度 l 再从3开始探索
for i in range(n+1-l): #从str的0号位置开始探索长度为3往上是否有回文子串，由 i+l-1=n得 i=n+1-l
r=i+l-1
if s[i]==s[r] and dp[i+1][r-1]: #若首尾两个字符i,r相同且去掉首尾字符后的子串仍为回文串则说明str[i:r]也是回文串
dp[i][r]=True
start, max_len = i, l #因为每次都更新最长回文子串的开始索引start，所以最终该方法得到的最长回文子串是位置比较靠后的那个答案
return s[start : start+max_len]
# 马拉车算法
# 先在字符串中间加符号隔开，使得奇偶回文数的形式统一
# 然后用kmp的思想去优化中心扩散
if len(s)== 0:return ""
s_new = '#' + '#'.join(s) + '#'
#print(s_new)
#已遍历的最大右边界
mx = 0
#对应的中心点
mid = 0
l = len(s_new)
# 扩散半径数组，初始值1或者0都可以，只是代表刚开始的时候扩散半径是多少而已
p = [1]*l
for i in range(l):
if i<mx:
# 这个时候可以用已经计算过的值
# 不能超过已遍历的右边界
# i对应的镜像 = 2*mid - i
# 由mx定义可知半径最长不会超过mx-i
p[i] = min(mx-i,p[2*mid-i])
# 主要的优化已经在上面节省了时间，接下来就是正常的扩散
while( i-p[i]>=0 and i+p[i]<l and s_new[i-p[i]] == s_new[i+p[i]]):
p[i] += 1
# 记录一下mx和mid
if i+p[i] > mx:
mx = i+p[i]
mid = i
maxr = max(p)
ans = p.index(maxr)
# 因为跳出循环的时候多加了1，所以实际上的扩散半径应该减1
maxr -= 1
return s_new[ans-maxr:ans+maxr+1].replace('#',"")
# # 作者：clay001
# # 链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/bu-chong-guan-fang-ti-jie-zuo-yi-dian-wei-xiao-de-/
class Solution:
def countSubstrings(self, s: str) -> int:
'''
使用动态规划来进行解决： O(n^2), O(n^2)
状态：dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
状态转移方程：当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时，dp[i][j]=true，否则为false
这个状态转移方程是什么意思呢？
当只有一个字符时，比如a自然是一个回文串。
当有两个字符时，如果是相等的，比如aa，也是一个回文串。
当有三个及以上字符时，比如ababa这个字符记作串1，把两边的a去掉，也就是bab记作串2，可以看出只要串2是一个回文串，那么左右各多了一个a的串1必定也是回文串。所以当s[i]==s[j]时，自然要看dp[i+1][j-1]是不是一个回文串
'''
res = 0
n = len(s)
dp = [[False]*n for _ in range(n)]
for j in range(n):
for i in range(j+1): #i在j的前面
if s[i] == s[j] and (j-i<2 or dp[i+1][j-1]):
dp[i][j] = True
res += 1
return res
'''
中心扩散法： O(n^2), O(1)
为什么有 2 * len - 1 个中心点？
aba 有5个中心点，分别是 a、b、c、ab、ba
abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba
什么是中心点？
中心点即left指针和right指针初始化指向的地方，可能是一个也可能是两个
为什么不可能是三个或者更多？
因为3个可以由1个扩展一次得到，4个可以由两个扩展一次得到
'''
N = len(s)
ans = 0
for center in range(2*N - 1):
left = center // 2
right = left + center % 2
while left >= 0 and right < N and s[left] == s[right]:
ans += 1
left -= 1
right += 1
return ans
class Solution:
def shortestPalindrome(self, s: str) -> str:
hi = len(s)
while hi > 0:
if s[:hi] == s[:hi][::-1]:
break
hi -= 1
# s[hi:]s尾部不能使（s[:hi]）之回文的那一段
# 反转s[hi:]然后插入到s头部即可
return s[hi:][::-1] + s
5. 最长回文子串
5. 最长回文子串
5. 最长回文子串
5. 最长回文子串
5. 最长回文子串
