[파이썬 알고리즘 인터뷰] 문자열 조작 - 가장 긴 팰린드롬 부분 문자열

🐍 문제

가장 긴 팰린드롬 부분 문자열을 출력하라.

팰린드롬 : 거꾸로 읽어도 동일한 문자열 (출처 : 위키백과)

• 입력1
  "babad"
• 출력1
  "bab" or "aba"
• 입력2
  "cbbd"
• 출력2
  "bb"

🐍 내 풀이

중앙 문자를 중심으로 앞뒤로 문자열이 동일하다는 것을 이용하였다. 주어진 입력값에서 앞에서부터 순서대로 팰린드롬 문자열이 있는지 확인한다. 현재 문자가 중앙 문자라고 생각했을 때 한칸씩 이동하며 내 주위 문자들이 동일한지 판단한다. 팰린드롬 문자열인 경우 모두 리스트에 저장하여 최종적으로 문자열이 긴 것 하나만 출력한다. 출력값에 대한 상세한 정렬 기준이 없으므로 길이만 확인하였다.

palindrome = list()
string = "babad"

for idx, word in enumerate(string):
	for j in range(len(string) // 2):
		if idx - j < 0 or idx + j > len(string) - 1:
			break
		if string[idx - j] == string[idx + j]:
			palindrome.append(string[idx - j:idx + j + 1])
# palindrome : ['b', 'a', 'bab', 'b', 'aba', 'a', 'd']

answer = sorted(palindrome, key=len, reverse=True)[0]
# answer : 'bab'

🐍 교재 풀이

교재의 풀이를 확인하니 내가 홀수로 된 팰린드롬 문자열만 처리했다는 것을 알았다. 교재 풀이를 이용하면 짝수로 된 팰린드롬 문자열도 구할 수 있다.

현재 문자열을 기준으로 양쪽으로 확장한다는 것은 동일하나 '중앙값'을 두지않고 왼쪽과 오른쪽의 인덱스값만을 설정해 뻗어나가도록 하였다. 짝수 팰린드롬 문자열을 위해 i부터 i + 1까지, 홀수 팰린드롬 문자열을 위해 i부터 i + 2까지 값을 구하고 길이가 긴 것을 택한다.

max함수를 이용하여 더 간결하게 표현하였다.

def longestPalindrome(s):
	def expand(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) < 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 = "babad"
longestPalindrome(s)
#'bab'

s = "cbbd"
longestPalindrome(s)
#'bb'