Python
파이썬 알고리즘 인터뷰 - 06. 가장 긴 팰린드롬 부분 문자열
s코딩초보s
2022. 1. 10. 23:00
<--- 리트코드 5. Longest Palindrome Substring --->
# 문제: 가장 긴 팰린드롬 부분 문자열을 출력하라.
입력
| "babad" |
출력
| "bab" |
입력
| "cbbd" |
출력
| "bb" |
# 풀이
1. 중앙을 중심으로 확장하는 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def longest_palindrome(s):
# 팰린드롬 판별 및 투 포인터 확장
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]
# 해당 사항이 없을 때 빠르게 리턴
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
s = input()
print(longest_palindrome(s))
|
cs |