131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

令n为s的长度，那我们容易知道一共有2^(n-1)种可能的分割方式，如果采用暴力，对每一种可能我们需要线性时间判断是否是回文。我们可以用动态规划来缩短判断的时间。但由于我们还需要进行一些数组的拼接，字符串的复制操作，采用动态规划可以优化运行时间，但复杂度不会有数量级上的变化，始终是O(n2^n)。考虑空间复杂度，应该为O(n^2)

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        str_len = len(s)
        is_palindrome = [[False] * str_len for _ in range(str_len)]

        # initialise the 2D array
        for idx in range(str_len):
            is_palindrome[idx][idx] = True
            if idx + 1 < str_len:
                is_palindrome[idx][idx + 1] = s[idx] == s[idx + 1]

        # Update the array in such an order
        # 0-2, 1-3, 2-4, ..., n-3-n-1
        # 0-3, 1-4, 2-5, ..., n-4-n-1
        # ...
        # ...
        # 0-n-1
        for length in range(3, str_len + 1):
            for idx in range(0, str_len - length + 1):
                start = idx
                end = idx + length - 1
                is_palindrome[start][end] = is_palindrome[start + 1][end - 1] and s[start] == s[end]

        return self.getPartitionWithMemo(s, 0, is_palindrome)

    
    def getPartitionWithMemo(self, s, cur_idx, is_palindrome):
        if cur_idx == len(s):
            return [[]]

        result = list()
        first_sub_string = ”“
        for end_idx in range(cur_idx, len(s)):
            first_sub_string += s[end_idx]
            # if the first substring is palindrome
            if is_palindrome[cur_idx][end_idx]:
                # recursively get palindrome sub-strings for the rest part
                tmp_results = self.getPartitionWithMemo(s, end_idx + 1, is_palindrome)
                for each in tmp_results:
                    result.append([first_sub_string] + each)

        return result