문제
Given a string s, return the longest palindromic substring in s.주어진 문자열 s에 대해, 가장 긴 회문 형태의 부분문자열을 리턴하시오.
예시
Input: s = "babad"
Output: "bab"
Explanation: "aba" 또한 정답임.제한
- 1 <= s.length <= 1000
- s consist of only digits and English letters.
풀이법
1. Brute force
맨 처음으로는 모든 문자열의 경우의 수를 따져 회문인지 확인 한 뒤,
회문이면 배열에 저장해둔다.
모든 문자열의 검사가 끝나면, 회문인 부분문자열이 모두 저장되어 있을텐데,
이를 문자의 길이 기준으로 내림차순 정렬시 맨 첫번째 단어가 가장 긴 부분 문자열이 될 것이다.
그런데 보이는것과 같이 무식한 방법으로 일단 모든 문자열을 순회하는데 O(n^2)의 시간 복잡도가 소요
회문인지 확인하는데 O(n)의 시간복잡도가 소요되어
총 시간복잡도가 O(n^3) 이라는 아주 끔찍한 알고리즘이 된다.
당연히 시간 초과로 인해 풀리지 않는다.
def validPalindrome(s: str):
for i in range(0, len(s)//2):
if s[i] != s[len(s)-1-i]: return False
return True
class Solution:
def longestPalindrome(self, s: str) -> str:
lst = list()
for i in range(len(s)):
for j in range(i, len(s)):
newstr = s[i:j+1]
if validPalindrome(newstr): lst.append(newstr)
lst.sort(key=len, reverse=True)
return lst[0]2. Brute forse - Better version
1번의 풀이에서 배열부분을 변경한 코드이다.
문제에서는 가장 큰 부분문자열을 리턴하라고 했기 때문에, 애초에부터 가장 문자열이 큰것부터
조회를 하고, 이게 회문이 맞다면 그냥 바로 리턴하는 방식이다.
def validPalindrome(s: str):
for i in range(0, len(s)//2):
if s[i] != s[len(s)-1-i]: return False
return True
class Solution:
def longestPalindrome(self, s: str) -> str:
lst = list()
for i in range(1, len(s)):
for j in range(i):
if s[j] == s[j+len(s)-i] and validPalindrome(s[j:j+len(s)-i+1]):
return s[j:j+len(s)-i+1]
return s[0]
사실 이것도 실행 안될줄 알았는데 아슬아슬하게 시간제한을 통과해 제출은 가능했다.
시간 복잡도 자체는 O(n^3)으로 동일하나 테스트케이스가 운좋게 잘 들어맞은것으로 보인다.
3. 최적의 풀이법
최적의 풀이법은 반복과 동시에 회문임을 검사하는 것이다.
일단 회문이 되는 경우는 개인적으로 두가지가 있다고 생각하는데
문자열의 길이가 짝수인 경우와 홀수인 경우가 있다.
짝수인 경우는 중심점 없이 대칭이 되며
홀수의 경우는 중간의 글자가 일종의 축이 된다.
이를 이용해 왼쪽 중간점이 되는 부분을 시작으로 하여
점점 크기를 늘려나가 가장 큰 회문이 되도록 하는것을 찾도록 하는 함수를 만들어
모든 문자에 돌려보는것이다.
class Solution:
def longestPalindrome(self, s: str) -> str:
def lookup(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
if len(s) <= 1 or s == s[::-1]: return s
ans = ''
for i in range(len(s)-1):
ans = max(ans, lookup(s, i, i+1), lookup(s, i, i+2), key=len)
return ans
상위 98퍼센트의 성능이 나왔다.
시간복잡도는 O(n^2)가 된다.
