[Leet Code] longest-palindromic-substring

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

 

 

Solve

입력값이 다음과 같을 때

"babad"

 출력 예시는 다음과 같다.

"bab"

 주어진 문자열에서 가장 긴 팰린드롬의 부분 문자열을 출력하는 문제이다. 필자는 특출 난 알고리즘 기법을 아는 것이 아니기 때문에 무지성으로 정말 모든 부분 문자열을 구한 후 이를 List에 저장하고 가장 긴 문자열을 뽑아내는 방식으로 풀었다.

# 필자가 푼 방식
class Solution:
    def longestPalindrome(self, s: str) -> str:

        length = len(s)
        result = []

        if s == s[::-1]:
            return s

        for x in range(length):
            for y in range(length + 1):
                temp = s[x:y]

                if (temp == temp[::-1]) and temp:
                    result.append(temp)
        return max(result, key=len)

 

 

결과는 반쯤 예상했었지만 최악의 효율이다.

사실 필자가 푼 코드를 Leet Code에 그대로 제출하게 되면 거의 통과하지 못한다. 말 그대로 어쩌다 운이 좋아 통과한 셈으로 봐도 상관없다.

몇 번 시도해보다가 안되니까 다른 풀이는 어떤게 있나 하고 봤는데 필자랑 거의 같은 꼴로 푼 코드가 있어서 몇 번 Submit을 해서 통과했다.  다음 포스팅은 Two Pointer Sliding Window 이용해서 푸는 방법을 다뤄보기로 하고 이만 글을 마친다.