[파이썬 알고리즘] 6장 - 문자열 조작 (longest palindrome substring) ⭐

leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

 

<문제>

Given a string s, return the longest palindromic substring in s.

 

<예시>

Input: s = "babad"

Output: "bab"

Note: "aba" is also a valid answer.

 

Input: s = "cbbd"

Output: "bb"

 

Input: s = "a"

Output: "a"

 

---

# https://leetcode.com/problems/longest-palindromic-substring/

def solution_1(s):
    # time limit exceeded (비효율 코드)
    max_palindrom = ""
    for start_index in range(len(s)):
        for end_index in range(start_index+1, len(s)+1):
            if s[start_index:end_index] == s[start_index:end_index][::-1]:
                if len(max_palindrom) < end_index - start_index + 1:
                    max_palindrom = s[start_index:end_index]
    return max_palindrom


def solution_2(s):
    def expend(s, left, right):
        if right < len(s) and s[left] == s[right]:
            while (left-1 >= 0) and (right+1 < len(s)) and (s[left-1] == s[right+1]):
                left -= 1
                right += 1
            return s[left:right+1]
        return s[left]

    # max_len 이라는 변수를 둘 필요가 전혀 없다!
    max_palindrom = ""
    for i in range(len(s)):
        sub = expend(s, i, i)
        if len(sub) > len(max_palindrom):
            max_palindrom = sub

        sub = expend(s, i, i+1)
        if len(sub) > len(max_palindrom):
            max_palindrom = sub
    return max_palindrom


# best code!
# https://leetcode.com/problems/longest-palindromic-substring/discuss/2954/Python-easy-to-understand-solution-with-comments-(from-middle-to-two-ends).
def solution_3(s):
    def expend(s, left, right):
        while (0<=left) and (right<len(s)) and (s[left]==s[right]):
            left -= 1
            right += 1
        return s[left+1:right]

    max_palindrom = ""
    for i in range(len(s)):
        sub = expend(s, i, i)
        if len(sub) > len(max_palindrom):
            max_palindrom = sub

        sub = expend(s, i, i+1)
        if len(sub) > len(max_palindrom):
            max_palindrom = sub

    return max_palindrom

 

best code라고 생각하는 solution_3에 대해서만 리뷰를 진행하겠다.

palindrom이란 왼쪽에서 오른쪽으로 읽어도, 오른쪽에서 왼쪽으로 읽어도 같은 문자열을 말한다.

 

1. palindrom이 홀수 길이인 경우

• 하나의 character에서 왼쪽, 오른쪽으로 하나씩 확장을 한다.
• 양쪽으로 확장해서 여전히 palindrom이라면 다시 한 번 확장을 진행하고,
• palindrom이 아니라면 멈춘다.

2. palindrom이 짝수 길이인 경우

• 이웃한 두 character가 동일한 지 체크한다. 
• 동일하다면 양쪽으로 확장해서 여전히 palindrom인 지 확인하고, 그렇다면 다시 한 번 확장을 진행한다.
• 만약 palindrom이 아니라면 멈춘다.

 

이러한 확장을 수행하는 함수가 extend 함수이다.

1. 홀수 길이의 palindrom인 경우
   1. 길이 1의 palindrom : 첫 번째 while문은 통과하지만 그 다음 while은 통과하지 못한다 -> 글자 하나 반환
   2. 길이 3 이상의 palindrom : 길이 3 이상의 palindrom 반환
2. 짝수 길이의 palindrom인 경우
   1. 길이 0의 palindrom : 첫 번째 while문 조차 통과하지 못한다 -> 빈 문자열 반환
   2. 길이 2 이상의 palindrom : 길이 2 이상의 palindrom 반환

solution_3 내부에서는 extend에서 반환된 문자열의 길이가 max_palindrom의 길이보다 큰 지 판단한다.

만약 크다면 max_palindrom을 새로운 값으로 업데이트 한다.