최장 팰린드롬 문자열 찾기
https://leetcode.com/problems/longest-palindromic-substring/

22-05-25

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        
        for i in range(n-1):
            for j in range(0,i+1):
                ss = s[j:n-i+j]
                if ss == ss[::-1]:
                    return ss
                
        return s[0]

Time Limit Exceeded
현재 코드 계산량은 $n(n-1)/2.$
abcdef.(중략).xx 이런 경우, xx를 찾기위해서 $O(n^2)$의 작업을 해야함.

Next what to do
1. 짝수(2)-홀수(3) 투 포인터 사용
2. 작은 단위에서 확장하는 방식으로 코드 짜기

24-09-10

class Solution(object):


    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        def findPalindrome(s):
            if s == s[::-1]:
                return True
            else:
                return False

        def updatepalindrome(s, start, end, condition = True):

            while (start > 0) and (end < n) and condition:
                if findPalindrome(s[start-1:end+1]):
                    start -= 1
                    end += 1
                else:
                    condition = False

            return start, end

        def searchingPalindrome(s, start, end, palindrome): 

            if findPalindrome(s[start:end]): 
                updated_start, updated_end = updatepalindrome(s, start, end)

                palindrome = s[updated_start:updated_end] if len(palindrome) < (updated_end-updated_start) else palindrome

            return palindrome

        n = len(s)

        if n < 2:
            return s

        palindrome = s[0]
        
        for i in range(n-1):

                # even searching
                start, end = i, i+2
                palindrome = searchingPalindrome(s, start, end, palindrome)

                # odd searching
                start, end = i, i+3
                palindrome = searchingPalindrome(s, start, end, palindrome)

        return palindrome

1. input 길이가 2보다 짧은 경우, 예외 처리 진행
2. output을 주어진 인풋의 첫번째 글자로 시작함.
3. 첫번째 글짜부터 길이가 짝수인 팰린드롬, 홀수인 팰린드롬을 확인하여 output에 업데이트 함.

Next what to do
1. 빠르게 리턴하는 부분에서 한 글자인 경우, 전체 글자가 팰린드롬인 경우로 처리하자.
2. 코드 가독성 높히기
- palindrome = max(palindrome, searchingPalindrome(i, i+2), searchingPalindrome(i, i+3), key=len)
- line이 30줄 넘지 않도록 작성하자
3. 주의) 슬라이싱과 인덱스 조회에는 차이가 있다. 이를 잘 고려해서 작성할 것.