[Leetcode] 5. Longest Palindromic Substring

✅ 문제 - 가장 긴 팰린드롬 부분 문자열 구하기

💡 팰린드롬이란? 토마토 기러기 스위스처럼 앞으로 읽어도 거꾸로 읽어도 같은 문자열을 지닌 단어를 말한다.
주어진 문자열 s에서 앞뒤가 똑같은 문자열을 추출하여 가장 긴 것만 반환하는 것이 이 문제의 포인트이다.
주어진 문자열의 길이가 짝수인 경우 연달아 겹쳐있는 문자도 팰린드롬에 포함된다.

 

---

✅ 첫 번째 시도 - 실패

class Solution:
    def longestPalindrome(self, s: str) -> str:
        #한 글자일 경우, s를 뒤집었을 때 s와 같은 경우 s 그대로 반환
        if len(s) == 1 or s == s[::-1]: return s

        #팰린드롬 담을 리스트 선언
        p_list = []

        for i in range(len(s)):
            for j in range(i+1, len(s)):
                #i~j까지 문자열과 뒤집었을때 문자열 비교하여 일치하면 빈 리스트에 담음
                if s[i:j] == s[i:j][::-1]:
                    p_list.append(s[i:j])

        return max(p_list, key=len) #리스트에서 길이가 가장 긴 문자열 반환

💡 내가 잡은 Point

1. 문자열이 단 1글자일 경우, 문자열을 뒤집었을때 원래 문자열과 완전히 같을 경우는 바로 문자열 s 반환
2. 길이가 제각각인 팰린드롬 문자열을 담을 list 만들기
3. 문자열을 index별로 추출하여 거꾸로 뒤집었을때 같으면 list에 담기
4. list에서 길이가 가장 긴 문자열을 반환

---

 
이렇게 했더니 테스트코드 중  "babad", "cbbd"는 통과하였으나 문자열이 "abb"의 경우 "bb"를 출력해야 하는데 "a"가 출력됐다.
 

여기서 문제점

1. abb에서 a가 출력됐다는 것은 list에 담을 때부터 조건이 잘못 걸림
2. 중첩 for문으로 문자열을 2번이나 순회해야함
 
어떻게 해결할 것인가?
 

📌 solution 1) 리스트 이용

알고보니 두번째 for문에서 제대로 비교를 안하고 있었다. 문자열 s를 앞뒤 거꾸로 비교해야하는데 그 다음 문자랑만 비교를 하니까 당연히 긴 팰린드롬 문자열이 확인이 안되는 거였다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
   	#한 글자일 경우, s를 뒤집었을 때 s와 같은 경우 s 그대로 반환
        if len(s) == 1 or s == s[::-1]: return s

        p_list = []
		
        for i in range(len(s)):
            for j in range(len(s), i, -1):
            #i~j까지 문자열과 뒤집었을때 문자열 비교하여 일치하면 빈 리스트에 담음
                if s[i:j] == s[i:j][::-1]: 
                    p_list.append(s[i:j])

        return max(p_list, key=len)

거꾸로 확인하기 위해 for문의 범위를 뒤집어서 거꾸로 비교한 문자열과 온전히 비교 가능!
하지만 런타임이 8771ms, 메모리가 85.92MB로 성능 개선이 필요해 보인다.
 

---

 

✅📌 solution2) 투 포인터 이용

 

결과적으로 런타임 77ms, 메모리 17.4MB로 굉장히 성능 개선이 됐다.

def longestPalindrome(self, s: str) -> str:
		#한 글자일 경우, s를 뒤집었을 때 s와 같은 경우 s 그대로 반환
        if len(s) ==1 or s == s[::-1]: return s
        
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]



	# 문자열 길이가 가장 큰 값 result에 담아서 반환
        result = ''
        for i in range(len(s) - 1):
		#for문 돌리면서 현재 가장 문자열이 긴 단어 result에 담아서 함께 비교
            result = max(result, 
            		# 짝수인 경우 한 자리씩 비교
                         expand(i, i + 1), 
                         # 홀수인 경우 두 자리씩 비교
                         expand(i, i + 2),
                         key=len)
        return result

💡 투 포인터를 이용하여 양쪽 값을 동시에 비교하면서 팰린드롬 판별하기

 
사실 파이썬이 처음이기도 하고 투 포인터를 이용하는 방식이 너무 낯설어서 다른 사람의 코드와 설명을  열심히 뜯어봤다.
굉장히 도움이 됐던 건 이 분이 올린 설명 중 그림이었다. 
출처: https://dongjun-yi.github.io/posts/LongestPalindrome/
이 분의 그림을 열심히 따라 그리면서 노력한 끝에 이해했음...!
 

---

 
 
1. 아래 max 함수 안에서 expand 함수를 호출하여 가장 길이가 긴 문자열(key=len)을 result에 담아 반환
2. expand 함수
 1) left 포인터가 0 이상, right 포인터가 문자열의 길이보다
     작으면서 left right 인덱스의 문자가 같은 값일때 좌우로 포인터를 확장시켜 줘야 한다.
 2) s[left+1:right]는 인덱스가 left+1부터 right 이전까지! (right는 포함 되지 않는다!!)
 
 
 

expand 함수가 이해가지 않는다면 아래 그림을 참고해 보면 좋겠다.