Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Input: “cbbd”
Output: “bb”

생각의 흐름
일단 가장 쉬운 풀이를 생각해보았다. 시작점과 길이를 바꿔가면서 2중 for문으로 풀면 풀릴것같았다. 다만 중복 계산이 너무 많다. 이전에 계산했던 결과를 이용하면 그 다음 문제를 해결하는데 사용할 수 있다.

어떻게 하면 중복 계산을 제거할 수 있을까 고민하던 찰나에, 팰린드롬의 특성을 이용해보자는 생각이 들었다. 팰린드롬은 양끝을 제외한 가운데 부분이 팰린드롬이고 양끝이 같으면 그 부분은 팰린드롬이다. 이 점을 이용하면 중복 계산을 줄일 수 있을거란 생각이 들었다.

우선 2차원 배열을 선언한뒤, 시작점과 길이를 계속 바꿔가면서 문자열의 시작 인덱스와 끝 인덱스로 잘랐을때 해당 부분이 팰린드롬인지를 아닌지를 기록했다.

그럼 길이가 2일때 구해놨던 정보들이 길이가 3일때 해당 부분이 팰린드롬인지 판단할때 중복계산을 막아 줄 수 있기 때문에 어느정도 계산량을 줄일 수 있었다. 다만 이렇게 해도 퍼센티지가 너무 낮은걸 보니 별로 좋지 못한 풀이인것같다.