그 외: dp[lo][hi] = dp[lo + 1][hi - 1] and (s[lo] == s[hi])
내부가 palindrome 인지 && 양 끝의 두 문자가 같은지
lo + 1을 살펴보아야 하므로, lo는 오른쪽부터 순회해야 함
Idea 2: Two Pointer
palindrome에는 두 가지 종류가 있다.
홀수 길이: 가운데 문자는 확인 X
짝수 길이: 전부 확인
따라서, s의 모든 문자를 순회하며, 좌우로 확장해가면서 홀수 길이의 palindrome과 짝수 길이의 palindrome을 찾아 longest palindrome을 트래킹 하면 된다.
이때, 좌우로 확장하는 함수 expand(left, right)는 다음과 같이 작성한다.
def expand(left, right):
"""left, right를 양끝으로 늘려가며 palindrome을 찾는 함수"""
while left >= 0 and right <= n and s[left] == s[right - 1]:
left -= 1
right += 1
return s[left + 1:right - 1]
이를 다음과 같이 사용한다. max()를 사용할 때 문자열의 길이를 기준으로 해야하므로, key=len으로 설정한다.
result = ""
for i in range(n):
result = max(
result,
expand(i, i + 1), # 홀수 길이 palindrome 찾기
expand(i, i + 2), # 짝수 길이 palindrome 찾기
key=len
)
Approach
Idea 1: 2D DP
dp[lo][hi]
:lo
번째 문자 ~hi
번째 문자까지 palindrome 인지 여부케이스 나누기
lo == hi
일 때:dp[lo][hi] = True
hi == lo + 1
일 때:dp[lo][hi] = s[lo] == s[hi]
그 외:
dp[lo][hi] = dp[lo + 1][hi - 1] and (s[lo] == s[hi])
lo + 1
을 살펴보아야 하므로,lo
는 오른쪽부터 순회해야 함Idea 2: Two Pointer
palindrome에는 두 가지 종류가 있다.
따라서,
s
의 모든 문자를 순회하며, 좌우로 확장해가면서 홀수 길이의 palindrome과 짝수 길이의 palindrome을 찾아 longest palindrome을 트래킹 하면 된다.이때, 좌우로 확장하는 함수
expand(left, right)
는 다음과 같이 작성한다.이를 다음과 같이 사용한다.
max()
를 사용할 때 문자열의 길이를 기준으로 해야하므로,key=len
으로 설정한다.이 방법이 DP 보다 훨씬 효율성이 좋았다.
Complexity
O(n^2)
/ (Two-Pointer)O(n^2)
O(n^2)
/ (Two-Pointer)O(1)