[LeetCode] 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.

Example 1:

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

Example 2:

Input: "cbbd" Output: "bb"

 

Approach

Brute force로 접근. 인풋 스트링 길이에 해당하는 substring부터 길이를 1씩 줄이며 찾아나감

시간복잡도 O(n^3)

 

Optimization

Dynamic Programming O(n^2)

추가: Palindrome은 어떤 string이 palindrome일때 앞 뒤로 한 글자씩 늘려서 그 글자들이 같으면 역시 palindrome을 만족

이를 이용해 string의 중심문자를 설정하고 앞 뒤로 한 글자씩 늘리고 그 글자들이 같은지 확인하는 방식으로 palindrome string 길이를 늘림

중심문자는 문장길이가 홀수일때 한글자, 짝수일때 두 글자로 설정

이를 이용하면 O(n^2)만에 풀 수있음

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestPalindromicSubstring.cpp

chi3236/algorithm

https://github.com/chi3236/algorithm/blob/master/LeetCode_LongestPalindromicSubstring_DP.cpp

chi3236/algorithm