5. Longest Palindromic Substring

가장 긴 대칭 문자열을 찾는 문제이다. (길이 같은 것이 많을 경우 가장 앞에 있는 문자열)

 

중앙에서 대칭인 문자열이므로, 내가 지정한 문자에서 대칭이 된다면 그 지점부터 양쪽으로 넓혀나가며 비교를 하여 대칭문자열을 구하는 방법을 생각하였다.

대칭 문자열에는 위의 그림과 같이 두가지 유형이 있다. 따라서 각각 따로 for문을 만들어서 검사를 할 것이다.

• 홀수형

첫번째 문자부터 시작하여 i번째와 i+2번째의 문자가 같을 경우, 대칭문자열의 시발점이 되므로 k--와l++을 이용하여 양쪽으로 넓혀나가며 비교해준다.

 

• 짝수형

첫번째 문자부터 시작하여 i번째와 i+1번째의 문자가 같을 경우, 대칭문자열의 시발점이 되므로 k--와l++을 이용하여 양쪽으로 넓혀나가며 비교해준다.

 

문자열을 출력해야하므로 각각의 문자를 리스트에 문자에 해당하는 인덱스에 숫자 1를 넣어 기억을 시켜주었고, 가장 긴 문자열은 mbox라는 리스트에 따로 숫자를 복사하였다. 그리고 마지막에는 이를 result 리스트에 문자를 넣어주었다.

 

 

** 문제를 푸는데 실수한 점

 

1. 맨 앞에서 i와 i+2 번째 값을 비교하면서 문자열의 크기가 1과2인 경우 out of index가 발생하였다. 이를 예외처리 해야한다는 생각을 처음에 못했다.
2. 출력을 str로 해야하는데 리스트로 출력이 되었다. 예) 답: abc, 출력: 'a','b','c' -> ' '.join(result)로 리스트 원소들을 공백없이 붙였다.
3. 리스트 초기화 [0] * 1001 신경 못썼다.
4. 길이 체크하는 maxi과 cnt, 대칭문자열 체크하는 리스트 mbox, box를 같이 써서 소스가 너무 복잡해졌다.               -> mbox,box를 쓴 이유는 문자열 저장할 때 insert(0,s[k])와append(s[l])를 쓴다면 insert 명령어에서 오른쪽으로 문 자들이 밀리면서 시간복잡도가 증가할 것이라 생각했다.

 

 

소스코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        mbox= [0] * 1001
        maxi = 1
        if len(s) == 1:
            return s
        if len(s) == 2:
            if s[0] == s[1]:
                return s
            else: return s[0]
        for i in range(len(s)-2):
            if s[i] == s[i+2]:
                box = [0]*1001
                cnt = 1
                k = i
                l = i+2
                box[k+1] = 1
                while k>=0 and l<=(len(s)-1):
                    if s[k] == s[l]:
                        cnt += 2
                        box[k] = 1
                        box[l] = 1
                        k -= 1
                        l += 1
                    else: break
                if maxi < cnt:
                    mbox = box[:]
                    maxi = cnt
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                box = [0]*1001
                cnt = 0
                k = i
                l = i+1
                box[k+1] = 1
                while k>=0 and l<=(len(s)-1):
                    if s[k] == s[l]:
                        cnt += 2
                        box[k] = 1
                        box[l] = 1
                        k -= 1
                        l += 1
                    else: break
                if maxi < cnt:
                    mbox = box[:]
                    maxi = cnt
        result = []
        for i in range(len(s)):
            if mbox[i] == 1:
                result.append(s[i])
        if len(result) == 0:
            return s[0]
        return ''.join(result)