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:
https://gist.github.com/adamkorg/d743bd068ed0bdcff060d25e5f905ec0
Recursive with DP:
https://gist.github.com/adamkorg/a2a6079ae2c3f300ee99e98594b6252a
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.