leetcode 5번 Longest_palindrom

해당 문제는 문자열 s가 들어왔을때 가장 긴 palindrom을 찾는것이다. palindrom이란 회문으로 "토마토" , "기러기" 처럼 거꾸로해도 같은 말을 의미한다.

해당문제는 이번주 leetcode를 풀면서 가장 어려웠던 문제다 각설하고 해설해보겠다.

항상 느끼는 거지만 남의 코드가 제일 어렵다. 이번에도 천천히 해보자.

 

첫째로 예외처리이다. 만약 애초부터 입력 s가 회문구조이면 이것은 그냥 리턴하는 것이다. 이렇게 되면 s의 길이가 1일때 2일때도 다 처리할수 있다. 

 

내가 현재 사용하려는 방법은 어떤 글자를 기준으로 왼쪽 한글자와 오른쪽 한글자를 포함하여 회문이면 더 넓혀서 또 회문인가를 찾는것이다. 

그럼 회문의 구조는 어떻게 생기는 것일까?

case1 : bb (길이가 짝수인 경우)

case2 : bab (길이가 홀수인 경우)

case3 : b

이렇게 경우를 나눠볼 수 있을 것이다. (단, 글자가 하나인 경우 case3은 이미 s == s[::-1]에 해당되니 생략하겠다.)

case1 인 경우를 우선 살펴보자.

"aaeeaa" 과 같은 경우가 있다. 이  경우 2번째 index e와 3번째 index e가 같고 1번째 index a와 4번째 index a가 같은 것을 볼 수 있다. 이런 경우 일때는 expand(i, i+2)를 해주어 for문의 i가 2까지 되었을때 가장 긴 회문 구조를 찾을 수 있다.

 

case2 인 경우를 살펴보자.

"babab" 와 같은 경우를 살펴 볼 수 있을 텐데 이 경우는 expand(i, i+1) 을 해주어 2번째 index 인 b를 기준으로 회문구조로 이루어 진것을 알 수 있다. 그리고 s[left] == s[right-1] 이 부분도 상당히 헷갈릴텐데 이 부분은 expand(i, i+2) 인 경우 right-1 때문에 처음에는 사실상 i 와 i+1을 비교하는 형태가 된다. 또한 expand(i, i+1) 은 처음엔 i와 i 를 비교하는 형태가 된다.

 

마지막으로 for문을 설명하겠다. for 문은 인풋 s에 있는 모든 글자를 다 탐색할 목적으로 사용된 함수 이다. 즉 첫번째 글자를 기준으로 회문을 찾을 때, 두번쨰 글자를 기준으로 회문을 찾을 때 라고 생각하면 된다. 마지막으로 max 함수에 key로 len을 넣어주어 가장 긴 문자열을 result에 결과값으로 넣는 형태가 된다.