: 5. Longest Palindromic Substring
: 給一個字串s，回傳最長的子字串，其順序跟倒序長一樣。
: Input: s = "babad"
: Output: "bab" 或 "aba"
想法：
感覺可以用DP寫，但我DP不好@@
改用回文特性中心擴散法
從中間檢查兩邊index+i, index-i是否相等，來判斷是否是回文
如果是回文的話順便算一下是否是目前最大
然後迭代每個index找出最大值
奇數很好懂 就是index-i, index+i
偶數推了一下 每次檢查index-i, index+i-1
如果不是就break(利用odd_continue/even_continue兩個Flag控制)
Python死腦筋的用了while if 寫來寫去，不小心遇到邊界陷阱
C++改用function包起來簡單美觀多了
========== Python
class Solution:
def longestPalindrome(self, s: str) -> str:
maxLen = 0
maxret = ""
for i in range(len(s)):
j = 0
odd_continue = True
even_continue = True
while(i - j >= 0 and i + j - 1 < len(s)):
if (odd_continue and i+j < len(s) and s[i-j] == s[i+j]):
if maxLen < 2*j + 1:
maxret = s[i-j: i+j+1]
maxLen = 2*j + 1
else:
odd_continue = False
if (j > 0):
if (even_continue and s[i-j] == s[i+j-1]):
if maxLen < 2*j:
maxret = s[i-j: i+j]
maxLen = 2*j
else:
even_continue = False
if (not odd_continue and not even_continue):
break
j += 1
return maxret
=========== C++
class Solution {
public:
string longestPalindrome(string s) {
int maxLen = 0;
string maxString = "";
for (int i = 0; i < s.size(); ++i)
{
vector<int> res = findMaxPalindrome(s, i, i);
int st = res[0];
int end = res[1];
if (end - st + 1 > maxLen)
{
maxLen = end - st + 1;
maxString = s.substr(st, end-st+1);
}
res = findMaxPalindrome(s, i, i+1);
st = res[0];
end = res[1];
if (end - st + 1 > maxLen)
{
maxLen = end - st + 1;
maxString = s.substr(st, end-st+1);
}
}
return maxString;
}
vector<int> findMaxPalindrome(string s, int center, int center2)
{
int count = 0;
while(center >= 0 && center2 < s.size())
{
if (s[center] == s[center2])
{
count++;
center