“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/longest-palindromic-substring/
주어진 문자열 중에서 가장 긴 팰린드롬 서브스트링을 구하는 문제이다. 아… 이 문제부터 어려워지는 걸까. 해결 방법이 바로 떠오르지 않았다. 팰린드롬을 정규표현식으로 정의할 수 있으면 좋겠는데 그건 아마 안 되겠지… 문자 하나 하나 씩 무식하게 확인하는 수밖에 떠오르지 않았다. 어쩔 수 없이 바로 풀이로 넘어가자면,
class Solution:
def longestPalindrome(self, s: str) -> str:
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]
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- 첫 문자부터 두 문자, 세 문자 씩 확인해서 회문(팰린드롬)인지 확인한다.
- 회문일 경우 해당 문자의 좌우로 1씩 확장(좌측 -1, 우측 +1)하며 회문인지 확인하며 아닐 때까지 반복, 반환한다.
예를 들어 “123454321”가 주어질 때, 3문자 짜리 회문과 2문자 짜리 회문을 같이 확인해 나간다.
3문자(i~i+2): “123” -> “234” -> “345” -> “454” 에서 회문이므로 “34543”, “2345432”, “123454321”로 확장, 반환
2문자(i~i+1): “12” -> “23” -> “34” -> “45” -> … -> “21”로 회문 없음
결과는 “123454321”이다.
동적 프로그래밍으로 해결 가능하다고 하는데 그게 뭔지 기억이 나질 않는다. 다시 조금씩 해나가는 수밖에 없다.
그리고 이번 문제는 책에 있는 코드에 오타가 많아서 쓸데없이 고민한다고 시간을 많이 썼다. 정오표 확인하기를 잘했다. 알고리즘 책의 코드에 오자라니…