Python solution with detailed explanation


  • 0
    G

    Solution

    Palindrome Partitioning https://leetcode.com/problems/palindrome-partitioning/

    Algorithm

    • Standard backtracking solution.
    • Notice how the cache for is_palindrome is prepared in a DP fashion from lengths of 1,2,3,4..substrings.
    • Iterate from index k to len(s)-1 (say index i) and when we find a left palindrome indicated by cache[k,i], we add the left palindrome to so_far array and recursively call for i+1.
    • Terminating condition is k == len(s).
    class Solution(object):
        def is_palindrome(self, s):
            N = len(s)
            cache = [[False]*N for _ in range(N)]
            for i in range(N):
                cache[i][i] = True
                if i+1 < N:
                    cache[i][i+1] = (s[i] == s[i+1])
            for length in range(3,len(s)+1):
                j = length-1
                for i in range(N):
                    if i+j < N:
                        cache[i][i+j] = cache[i+1][i+j-1] and (s[i] == s[i+j])
            return cache
        
        def partition(self, s):
            """
            :type s: str
            :rtype: List[List[str]]
            """
            result = []
            self.helper(0, s, self.is_palindrome(s), [], result)
            return result
        
        def helper(self, k, s, cache, so_far, result):
            if k == len(s):
                result.append([x for x in so_far])
            else:
                for i in range(k, len(s)):
                    if cache[k][i]:
                        so_far.append(s[k:i+1])
                        self.helper(i+1, s, cache, so_far, result)
                        so_far.pop()
            return
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.