Programmers - 가장 긴 팰린드롬

문제 링크

모든 경우를 최적화 없이 하나씩 다 계산하게 되면 시간초과가 나게 된다.
(문자열의 길이가 n일 때 : Substring이 (n^2)/2개 , 팰린드롬 계산이 O(n), 총 O(n^3))

따라서 메모이제이션을 이용해 계산했던 결과를 기록하고 이를 사용해야 한다.

p[st][ed] = st번째 부터 ed번째 까지 의 부분문자열의 팰린드롬 여부.
p[st][ed] = p[st+1][ed-1] 이 팰린드롬인 경우, 문자열의 st번째와 ed번째가 같은지만 확인하면 p[st][ed] 가 팰린드롬인지 알 수 있다.

p[st+1][ed-1] 이 팰린드롬이 아닌 경우일때만 해당 부분문자열을 하나씩 비교하면서 판단한다.

처음에는

for st in range(n):
	for ed in range(st,n):
    	...

으로 탐색을 했는데 문자열의 길이가 클 때 재귀호출 depth가 많아져서 RecursionError가 발생해서
길이순서대로 탐색하도록 변경하였다.

def solution(s):
    n = len(s)
    p = [[-1 for _ in range(n)] for __ in range(n)]

    def is_palindrome(st, ed):
        if p[st][ed] != -1:
            return p[st][ed]

        if st == ed:
            p[st][ed] = 1
            return p[st][ed]

        if st + 1 == ed:
            p[st][ed] = 1 if s[st] == s[ed] else 0
            return p[st][ed]

        if st >= 1:
            if is_palindrome(st+1, ed-1) and s[st] == s[ed]:
                p[st][ed] = 1
                return p[st][ed]

        # 새로 생성된 palindrome인 경우
        sub = s[st:ed+1]
        for i in range(len(sub)//2):
            if sub[i] != sub[len(sub)-1-i]:
                p[st][ed] = 0
                return p[st][ed]
        p[st][ed] = 1
        return p[st][ed]

    answer = 0
    # 길이 순서대로 탐색하도록 변경
    for length in range(1, n+1):
        for st in range(n):
            ed = st+length-1
            if ed >= n:
                break
            p[st][ed] = is_palindrome(st, ed)
            if p[st][ed] == 1:
                answer = max(answer, ed-st+1)

    return answer