CS ﹒ Algorithm/Leetcode
2023. 1. 22.
LeetCode : Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/ 가장 긴 팰린드롬 문자열을 찾아내는 문제로, 팰린드롬 문자열이란 뒤집어도 똑같은 글자가 나오는 것을 의미한다. 대표적으로 기러기, 삐삐, 이효리(아님) 같은 것들이 해당된다. 한 글자도 팰린드롬이다. 가장 쉬운 방법은 3중 반복문을 활용하는 것이고, 시간복잡도를 제한하는 문제가 아니라면 모두 정답으로 허용해주는 릿코드라서 3중 반복문으로도 통과할 수 있을 것 같다. 근데 반복문이 3개 들어가면 자존심에 스크래치가 나니까 DP를 활용해보자. 거지같이 그려도 찰떡같이 알아들을 거라고 믿습니다. 이렇게 2중 배열을 만들었을 때, 행은 각 문자열, 열은 해당 문자열에서 어디까지가 팰린드롬인지를 저장한다...
