이 문제는 난이도가 너무 높아서 해결하지 못했다. 따라서 파이썬 알고리즘 인터뷰 책을 참고하였다.

문제

→가장 긴 팰린드롬 부분 문자열 출력하기

→ ex)

→ 입력값 : ‘babad’

→ 출력값 : ‘bab’

팰린드롬?

→ 앞으로해도 거꾸로해도 똑같은 단어

→ ex)토마토 이효리(코드상 이효리는 아니긴 하다)

풀이

(1) 투포인트 슬라이딩 윈도우처럼 이동

→ 위 예시와 같이 두 포인터가 앞으로 전진한다.

→ 짝수와 홀수 모두 판별해야하기 때문에 포인터를 두개로 설정한다.

→ 코드

result = ''
for i in range(len(s) - 1):
    result = max(result, 
									expand(i, i + 1), 
									expand(i, i + 2), 
									key=len)

(2) 팰린드롬 판별 및 투 포인터 확장

→ 팰린드롬을 찾을 경우 가장 긴 문자열을 찾는다.

→ 조건

1. left 포인트가 0보다 크거나 같아야 함.
2. right 포인트가 전체 길이보다 작아야 함.
3. 문자열의 left와 right가 같아야 함.