5. Longest Palindromic Substring Python3

Yelim Kim·2021년 9월 14일
0
post-thumbnail

Problem

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.

My code

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]

Review

실행 결과 : Runtime(87ms), Memory(14.4MB)

[접근법]
속도 향상을 위해 단어 자체가 palindrome이면 바로 출력
예를 들어 "xabay"라는 단어에서 even은 "xb", "ab". "ba"처럼 한 칸씩 옮기면서 2개짜리의 펠린드롬을 찾는다.
odd는 "xab", "aba", bay"씩 옮기면서 펠린드롬을 찾는다. "aba"라는 펠린드롬을 찾았으면, 짝수는 뒤로 한글자 더 더하고, 홀수는 양쪽으로 더해서 더 긴 길이가 되는지 확인한다.
단어 길이를 점점 늘려가며 더 긴 펠린드롬을 찾는다.

[느낀점]
정말 모르면 미루지 말고 빠르게 답지를 보고 내 걸로 만드는 연습을 하자.
예외는 항상 맨 처음에
포인터 계산하는게 힘들다. 펠린드롬은 홀수와 짝수개수를 다르게 처리해야 한다.

profile
뜬금없지만 세계여행이 꿈입니다.

0개의 댓글