Leecode - 5. Logest Palindromic SubString

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

Longest Palindromic Substring - LeetCode

---

 

string s가 주어지고, 가장 긴 palindrome을 만족하는 substring을 구하는 문제

 

 

첫번째 풀이: Brute Force

언어: C++

 

기존에 Brute Force 방법으로 풀어보려 시도했고, 테스트코드에서는 어느정도 맞아 떨어지는 것을 볼 수 있었다.

하지만 Time Limit Exceeded 에러가 떴고 복잡도 계산을 해보니 O(n^3)이 나와 

문제에서 주어진 length를 토대로 계산해보면 10억정도의 계산을 하게 되어 Brute force로는 풀기 힘든 듯 했다.

 

 

이런저런것을 시도해보다가 결국 답지를 보게 되었는데

 

사용언어: java

 

답지에선 주어진 String을 substring으로 나누고 그 substring의 중간 인덱스부터 왼쪽 오른쪽으로 나아가며 palindrome임을 check해 풀어나가는 식으로 풀어나갔었다.

 

* 8번의 for루프는 어떤 서브스트링을 조작하는게 아닌 인덱스를 조작하는 부분이다.

 

다음과 같은 방식으로 풀어나간다.

 

expandFromMiddle

 

 

10번 라인에서는 expandFromMiddle 함수에 같은 i값을 left와 right에,

 

11번 라인에서는 left에 i, right에 i+1을 넣는것을 볼 수 있는데

 

이는 이는 racecar와 같은 경우에 중간에 있는 'e'가 왼쪽과 오른쪽으로 expand할 때 처리하기 애매해지기 때문에 따로 처리하기 위함이다. 

 

 

11번 라인같은 경우는 다음과 같은 방식으로 풀어나간다.

 

 

 처음에 아예 중간이 아닌 'e'를 포함하고서 시작하는 것을 볼 수 있다.

이렇게 10번 라인과 11번 라인을 통해 각각 값을 구하면 둘 중 하나의 값은 맞을 것이다.

12번 라인에서 max함수를 통해 둘 중에 맞는 값을 구한 뒤 substring의 start와 end를 설정해준 다음에 return 해줌으로써 답을 구했다.

---

Reference

youtube.com/watch?v=y2BD4MJqV20&t=614s