[Two Pointer] 5. Leetcode - Longest Paildrome Substring

문제 링크

원래 나의 풀이

펠린드롬 여부를 판단하는 isPalindrome 함수를 생성, 부분문자열을 길이가 긴 것부터 차례로 펠린드롬 여부를 판단한다. 만약 펠린드롬이라면 모든 return하여 그 함수를 종료한다.

### leetcode 5
## Longest_Paildrome_Substring
# 가장 긴 팰린드롬 부분 문자열을 출력하라. 

class Solution:
   
    def longestPalindrome(self, s: str) -> str:
        
        def ispalidrome(str1):
            if str1 == str1[::-1]:
                return True
        
            return False
        
        for i in range(len(s),0,-1):
            for j in range(len(s) - i+1):
                if ispalidrome(s[j:j+i]):
                    return s[j:j+i]

runtime

Memory

투포인터를 이용한 풀이

주로 펠린드롬을 평가하기 위해서는 두가지 부류로 나눌 수 있다.

1) 'bb'와 같이 길이가 짝수인 형태의 펠린드롬
2) 'bab'와 같이 길이가 홀수인 형태의 펠린드롬

즉, "babad"라는 문자열을 탐색을 할 때

홀수인 길이의 펠린드롬 여부 검사, 짝수 길이의 펠린드롬 여부 검사를 동시에 하여 가장 긴 길이의 문자열을 찾는다.

따라서 expand함수를 통해서 이 펠린드롬 여부를 판단하고

• 펠린드롬이라면 리턴값이 있지만
• 펠린드롬이 아니라면 리턴값이 s[left + 1: right -1] 즉, left + 1 == right - 1이 같아지기 때문에 리턴값이 따로 도출되지 않는다.

#펠린드롬 여부 판단
def expand(left, right):
    while left >= 0  and right <= len(s) and s[left] == s[right-1]:
        left -= 1
        right += 1

    return s[left + 1: right - 1]

전체 풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0  and right <= len(s) and s[left] == s[right-1]:
                left -= 1
                right += 1

            return s[left + 1: right - 1]

        # 길이가 2보다 작을 경우 그 단어는 펠린드롬이다.
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ""
        
        for i in range(len(s)-1):
            result = max(result, expand(i,i+1), expand(i,i+2), key=len)
        
        return result

• expand(i,i+1)을 통해 'bab'와 같은 홀수 길이의 펠린드롬을 검사
• expand(i,i+2)을 통해 'bb'와 같은 짝수 길이의 펠린드롬을 검사

결과

Runtime 결과

Memory 결과

원래 실행 결과에 비해 메모리와 실행시간을 상당히 줄일 수 있었다,