[문자열] 리트코드 5: Longest Palindromic Substring
사용 언어: python 3.9.5
❓ Problem
문제 설명
https://leetcode.com/problems/longest-palindromic-substring/
가장 긴 팰린드롬 부분 문자열을 반환하시오.
난이도
Medium
🚩 Solution
시도 01)
1. 접근법
2개, 3개씩 슬라이딩 해나간다.
슬라이딩 윈도우 안이 팰린드롬이면 윈도우 영역을 넓혀간다.
2. 코드
class Solution:
def longestPalindrome(self, s: str) -> str:
def check_palindrome(left, right):
# s 인덱스 범위 벗어나는 경우
if not (left >= 0 and right < len(s)):
return ""
# 양 옆으로 한 칸씩 늘리며 같은지 확인
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
left += 1
# 팰린드롬 부분 리턴
return s[left:right]
# 예외처리 (길이가 2 이하인 문자열)
if (len(s) == 1) or (len(s) == 2 and s[0] == s[1]):
return s
elif len(s) == 2 and s[0] != s[1]:
return s[0]
# 팰린드롬 찾기
result = ""
for i in range(len(s)-1):
result = max(check_palindrome(i, i+1), # 짝수 길이 팰린드롬
check_palindrome(i, i+2), # 홀수 길이 팰린드롬
result,
key=len)
return result
3. 시간복잡도
4. 결과
성공: 테스트 2회, 제출 1회
메모리: 14.3 MB, less than 81.37%
시간: 992 ms, faster than 70.09%
5. 소요 시간
시작: 21.09.24 10:50
끝: 21.09.24 11:26
📕 피드백
1. 검색한 내용
2. 실수
result = max(result, another)에서
result 객체를 초기화하지 않고 max안에 파라미터로 넣어서 오류 생김
3. 발전 방향 (개선/추가사항)
Author And Source
이 문제에 관하여([문자열] 리트코드 5: Longest Palindromic Substring), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ember/문자열-리트코드-5-Longest-Palindromic-Substring저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)