Leetcode 132: Palindrome Partitioning II

The obvious fairly simple recursive solution is very slow (exponential). The recursive base case start->end is 1 char or isPalindrome(start->end) return 0 cuts. In the recursive function we go through each character in the range trying to place a cut and recurse left and right of the cut. Keep track of each return and set minCuts return if smaller. We can apply DP to that recursive solution to get O(n^3) but that is still too slow for the leetcode test cases. An iterative DP O(n^2) solution does pass the leetcode test cases.

The simple slow recursive solution:
Recursive with DP:
And below is the iterative DP solution:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.