Re: [閒聊] 每日LeetCode已回收
: 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--;
center2++;
}
else
{
break;
}
}
center++;
center2--;
return {center, center2};
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.12.199 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698427714.A.427.html
推
10/28 01:34,
2年前
, 1F
10/28 01:34, 1F
→
10/28 02:04,
2年前
, 2F
10/28 02:04, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 470 之 719 篇)：