알고리즘 연습 [가장 긴 팰린드롬]
가장 긴 팰린드롬
문제
앞뒤를 뒤집어도 똑같은 문자열을 palindrome이라고 합니다.
longest_palindrom함수는 문자열 s를 매개변수로 입력받습니다.
s의 부분문자열중 가장 긴 palindrom의 길이를 리턴하는 함수를 완성하세요.
예를들어 s가 토마토맛토마토이면 7을 리턴하고 토마토맛있어이면 3을 리턴합니다.
나의 풀이
def longest_palindrom(s):
# 함수를 완성하세요
result = []
for i in range(len(s)):
for j in range(i+2, len(s)+1):
if s[i:j] == s[i:j][::-1]:
result.append(len(s[i:j]))
return max(result)
단어를 전체 길이까지 2중 for문으로 끊어서 거꾸로 뒤집었을 때 같은 단어의 길이를 리스트에 넣은 다음 가장 긴 값을 return 함.
다른 풀이
def longest_palindrom(s):
return len(s) if s == s[::-1] else max(longest_palindrom(s[:-1]), longest_palindrom(s[1:]))
재귀를 사용할 수도 있었다. 다만 중복되는 값을 너무 많이 비교하는 듯