[LeetCode] 5. Longest Palindromic Substring

LeetCode 5번 Longest Palindromic Substring

String, DP, 확장

 

---

 

문제

 

유명한 팰린드롬 문제

팰린드롬(palindrome)이란? 'aba', 'eye' 처럼 거꾸로 읽어도 똑같은 문장이나 단어를 뜻한다.

 

 

과정

주어진 문자열s를 특정 기준에 따라 분리하고 별도로 팰린드롬인지 판별하는 함수를 만들어 분리된 문자열이 팰린드롬인지 체크하였다.

 

1. check_palindrome() 함수

해당 문자열이 팰린드롬이지 판별하는 함수이다.

 

1-1)  매개변수로 잘려진 문자열s가 들어오는 경우

 

def check_palindromic(s):
    mid = len(s) // 2 
    if len(s) % 2 == 0:    # 짝수
        reversed_s = reversed(list(s[mid:]))
        reversed_s = ''.join(reversed_s)
        if s[0:mid] == reversed_s:
            return True
    else:    # 홀수
        reversed_s = reversed(list(s[mid+1:]))
        reversed_s = ''.join(reversed_s)
        if s[0:mid] == reversed_s:
            return True
    return False

 

짝수와 홀수를 나눠서 문자열을 반절로 나누었다.

list의 reversed 함수를 사용하기 위해 하나의 문자열을 list변환 -> reversed 적용 -> 문자열로 변환의 작업을 거쳐줬다.

이후 두개의 문자열을 비교해서 같으면 True, 다르면 False로 반환하도록 했다.

 

이렇게 해도 정답을 구하는데에 있어서 문제는 없지만 여러번의 변한 작업과 slicing 작업으로 속도가 떨어지게 된다.

그래서 문자열s를 보내지말고 아예 시작(start)과 끝(end)의 인덱스를 보내도록 바꿧다.

 

 

1-2) 매개변수로 index가 들어오는 경우

 

def check_palindrome(start, end):
    end = end - 1
    while start < end:
        if s[start] != s[end]:
            return False
        start += 1
        end -= 1
    return True

 

이렇게 시작(start)과 끝(end)를 보낸다면 위의 귀찮은 작업들이 필요없어진다.

 

로직도 살짝 바꿧는데 문자열의 양쪽 인덱스에서부터 가운데로 한칸씩 당겨져오면서 해당 문자가 같은지 비교한다.

한번이라도 다르면 False를 반환하게 된다.

 

 

 

2. 반복문

이 부분은 메인 함수부분이다.

팰린드롬 판별 함수에 어떠한 값을 보낼지 수행하는 부분이다.

 

2-1) 1부터 순서대로 모든 경우를 반복

 

def longestPalindrome(self, s: str) -> str:
    answer = ""
    for i in range(len(s)):
        for j in range(i+1, len(s)+1):
            if check_palindromic(s[i:j]):
                if len(s[i:j]) > len(answer): answer = s[i:j]
    return answer

 

처음에 1-1 코드를 작성하면서 같이 작성했던 코드다.

문자열을 팰린드롬 판별 함수에 매개변수로 보내줬다.

 

또한 2중 반복문을 보면 1의 길이부터 문자열 s에 대해서 순서대로 탐색함을 볼 수 있다.

이렇게 하게 되면 최악의 경우(맨 마지막의 값이 정답일 경우) 속도가 현저히 늘어난다.

 

해당 코드는 testcase 69번에서 Time Limit Exceeded 에러가 발생했다.

 

 

 

2-2) 최대 길이부터 1씩 감소하며 반복

 

answer = ""
for i in range(len(s), 0, -1):
    for j in range(0,len(s)-i+1):
        if check_palindrome(j,j+i):
            return s[j:j+i]

 

어차피 가장 큰 경우를 구해야 하므로 문자열이 될 수 있는 가장 큰 경우부터 반대로 순차적으로 내려가면서 계산하면 더 빠르게 답을 구할 수 있다.

 

 

예제 1번 같은 경우)

1. len(s)인 문자열의 길이가 5인 경우부터 s에서 s[0:5]를 먼저 본다.
2. s[0:5] = "babad"     # false
3. 답이 아니므로 문자열의 길이가 5인 경우는 하나밖에 없으므로 이번엔 1작은 4인 경우를 탐색한다.
4. s[0:4] = "baba"     # false
5. s[1:5] = "abad"     # false
6. 답이 아니므로 문자열의 길이가 4인 경우는 두개밖에 없으므로 이번에도 1을 감하여 3인 경우를 탐색한다.
7. s[0:3] = "bab"      # true 
8. 답이 나오게 되면 현재까지 될 수 있는 수중에서 가장 큰 수이며 더이상의 계산은 무의미하므로 현재 구한 답을 리턴한다.

 

 

소스코드

2-1 과 2-2를 합친 코드

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check_palindrome(start, end):
            end = end - 1
            while start < end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            return True

        answer = ""
        for i in range(len(s), 0, -1):
            for j in range(0,len(s)-i+1):
                if check_palindrome(j,j+i):
                    return s[j:j+i]

 

시간복잡도: O(N**3)

공간복잡도: O(1) 

 

 

 

이후 Editorial을 보는데 해당 문제는 dp를 적용해서 푸는 경우도 있었다.

 

※ DP를 적용한 경우

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = [0, 0]
        
        for i in range(n):
            dp[i][i] = True
        
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                ans = [i, i + 1]

        for diff in range(2, n):
            for i in range(n - diff):
                j = i + diff
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    ans = [i, j]

        i, j = ans
        return s[i:j + 1]

 

 

 

통과

 

 

---

 

 

// 2023-08-03 스터디 과제