5. Leetcode - Longest Paildrome Substring [투포인터]
원래 나의 풀이
펠린드롬 여부를 판단하는 isPalindrome 함수를 생성, 부분문자열을 길이가 긴 것부터 차례로 펠린드롬 여부를 판단한다. 만약 펠린드롬이라면 모든 return하여 그 함수를 종료한다.
### leetcode 5
## Longest_Paildrome_Substring
# 가장 긴 팰린드롬 부분 문자열을 출력하라.
class Solution:
def longestPalindrome(self, s: str) -> str:
def ispalidrome(str1):
if str1 == str1[::-1]:
return True
return False
for i in range(len(s),0,-1):
for j in range(len(s) - i+1):
if ispalidrome(s[j:j+i]):
return s[j:j+i]
runtime
Memory
투포인터를 이용한 풀이
주로 펠린드롬을 평가하기 위해서는 두가지 부류로 나눌 수 있다.
1) 'bb'와 같이 길이가 짝수인 형태의 펠린드롬
2) 'bab'와 같이 길이가 홀수인 형태의 펠린드롬
즉, "babad"라는 문자열을 탐색을 할 때
홀수인 길이의 펠린드롬 여부 검사, 짝수 길이의 펠린드롬 여부 검사를 동시에 하여 가장 긴 길이의 문자열을 찾는다.
따라서 expand함수를 통해서 이 펠린드롬 여부를 판단하고
- 펠린드롬이라면 리턴값이 있지만
- 펠린드롬이 아니라면 리턴값이 s[left + 1: right -1] 즉, left + 1 == right - 1이 같아지기 때문에 리턴값이 따로 도출되지 않는다.
#펠린드롬 여부 판단
def expand(left, right):
while left >= 0 and right <= len(s) and s[left] == s[right-1]:
left -= 1
right += 1
return s[left + 1: right - 1]
전체 풀이
class Solution:
def longestPalindrome(self, s: str) -> str:
def expand(left, right):
while left >= 0 and right <= len(s) and s[left] == s[right-1]:
left -= 1
right += 1
return s[left + 1: right - 1]
# 길이가 2보다 작을 경우 그 단어는 펠린드롬이다.
if len(s) < 2 or s == s[::-1]:
return s
result = ""
for i in range(len(s)-1):
result = max(result, expand(i,i+1), expand(i,i+2), key=len)
return result
- expand(i,i+1)을 통해 'bab'와 같은 홀수 길이의 펠린드롬을 검사
- expand(i,i+2)을 통해 'bb'와 같은 짝수 길이의 펠린드롬을 검사
결과
Runtime 결과
Memory 결과
원래 실행 결과에 비해 메모리와 실행시간을 상당히 줄일 수 있었다,
Author And Source
이 문제에 관하여(5. Leetcode - Longest Paildrome Substring [투포인터]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@turtle601/5.-Longest-Paildrome-Substring-투포인터저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)