Leet code - 5. Longest Palindromic Substring(Java)

leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

Q.

Answer

 

이전에 풀었었는데 다시 한번 풀려고하니 잘 풀리지가 않았다.

맨처음에는 checkPalindrome이라는 메소드를 만들어

 

스트링의 중간을 구한 뒤 좌측과 우측으로 확장하며 palindrome인 것을 check하도록 문제를 만들었었는데

O(n^3)의 시간복잡도가 나와 시간 초과가 나왔었다.

 

그래서 이 시간을 어떻게 줄일 수 있나 고민했고 다음과 같이 줄여냈다.

 

맨 처음엔 배열을 순회해서 substring을 반복해서 구해준 뒤 (O(n^2)의 시간복잡도) expandMiddle에서 한번 더 그 substring을 순회했기 때문에 시간이 오래 걸렸었다.

 

개선된 알고리즘의 경우

배열은 그대로 있고 미들인덱스의 값을 주고 거기서 좌측과 우측으로 확장시켜나가는 방식으로 풀게되었다.

이렇게 할 경우 String의 길이가 홀수인지 짝수인지에 따라서 적절한 값이 안나올 수 있는데 이는 14번 라인과 15번 라인 처럼 두개의 값을 구해주고 max를 해줘서 큰 값을 취하는 방식을 택했다.