Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Example 3:
Input: s = "a"
Output: "a"
Example 4:
Input: s = "ac"
Output: "a"
Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.
class Solution:
def longestPalindrome(self, s):
if s == s[::-1]: return s
cur_l, cur = 1, 1
for i in range(1, len(s)):
odd_l, even_l, r = i - cur - 1, i - cur, i + 1
odd, even = s[odd_l : r], s[even_l : r]
if odd_l >= 0 and odd == odd[::-1]:
cur_l = odd_l
cur += 2
elif even_l >= 0 and even == even[::-1]:
cur_l = even_l
cur += 1
return s[cur_l : cur_l + cur]
실행 결과 : Runtime(87ms), Memory(14.4MB)
[접근법]
속도 향상을 위해 단어 자체가 palindrome이면 바로 출력
예를 들어 "xabay"라는 단어에서 even은 "xb", "ab". "ba"처럼 한 칸씩 옮기면서 2개짜리의 펠린드롬을 찾는다.
odd는 "xab", "aba", bay"씩 옮기면서 펠린드롬을 찾는다. "aba"라는 펠린드롬을 찾았으면, 짝수는 뒤로 한글자 더 더하고, 홀수는 양쪽으로 더해서 더 긴 길이가 되는지 확인한다.
단어 길이를 점점 늘려가며 더 긴 펠린드롬을 찾는다.
[느낀점]
정말 모르면 미루지 말고 빠르게 답지를 보고 내 걸로 만드는 연습을 하자.
예외는 항상 맨 처음에
포인터 계산하는게 힘들다. 펠린드롬은 홀수와 짝수개수를 다르게 처리해야 한다.