[LeetCode OJ] Palindrome Partitioning - Medium Algorithm

<Problem Link>


<Comment>

먼저 문제를 이해해보면,
Palindrome : 회문, 앞에서부터 혹은 뒤에서부터 읽어도 문자배열이 같은 단어

자, 어떤 입력 문자열에 대해서,
생성 가능한 Palindrome 문자열만으로 이루어진 리스트의
모든 경우의 수를 만들어 2차원 리스트를 반환하는 것이 되겟다.

일단, 앞에서부터 한번 Palindrome 문자열을 만들기 위해 사용한 문자는 재사용이 되지 못하므로,
나같은 경우는 문자열의 시작 index에 따라 생성가능한 palindrome 문자열의 모든 경우를 다 미리 구해두고,
마지막에 Recursive를 통해 각 시작점에 따라 생성가능한 모든 palindrome list 경우의수를 생성하였다.

무려 시간복잡도가 N(입력문자열 길이)의 세제곱에 이르렀으나,
파이썬으로 submit한 알고리즘 중에서는 가장빨랐다능!?
하핫..;;

<Solution> Python - Accepted

================================================
실행시간 : 116ms
시간복잡도 : O(N^3)
공간복잡도 : O(N^2)
================================================

class Solution:
    # @param s, a string
    # @return a list of lists of string

    def partition(self, s):
# 해당 문자열의 시작점부터 생성가능한 Palindrome 문자열 리스트 얻음
        palin_dic = dict()
        for i in range(len(s)):
            palin_dic[i] = self.getPalindroms(s[i:]) 

# 재귀적으로 정답Set을 모은다.
        ret = []
        self.collect(ret, palin_dic, len(s), 0, []) 
        return ret


    def getPalindroms(self, s):
        ret = []
        s_len = len(s)
        for i in range(s_len):
            word = s[:s_len-i]
            if self.isPalindrome(word):
                ret.append(word)
        return ret


    def isPalindrome(self, s):
        sid = 0
        eid = len(s)-1
        ret = True
        while True:
            if sid > eid:
                break
            front = s[sid]
            back = s[eid]
            if front != back:
                ret = False
                break
            sid += 1
            eid -= 1
        return ret

        
    def collect(self, ret, palin_dic, idx_limit, start_idx, current_collection):
        append_list = palin_dic[start_idx]
        for palin_str in append_list:
            new_start_idx = start_idx + len(palin_str)
            new_collection = list(current_collection)  # 그냥 current_collection을 사용하면 안된다. (deep copy 사용)
            new_collection.append(palin_str)
            if new_start_idx >= idx_limit:
                ret.append(new_collection)
            else:
                self.collect(ret, palin_dic, idx_limit, new_start_idx, new_collection)



통계 위젯 (블랙)

18204
676
235523

GoogleAdsenseResponsive

Cluster map