Leetcode Q132 Palindrome Partitioning II (Hard)

Q132 Palindrome Partitioning II  Hard 
 


Prep work:
 isPalindrome[i][j]: a 2D array record is the substring(i, j) a palindrome

 minCuts[i]:  f(i) minimum cuts to make all substrings palindrome from f[i] - f[n-1]
 Initialise  minCuts[i] for the worst case:  f(i) = n - i - 1, means we cut every place we can

 Then we start backward from f[n-1] to optimise and keep updating isPalindrome[i][j] until we reach f[0] which is the final result 0 - the minimum cuts for the whole string to make all substring palindrome.

 Two dynamic programming happening here
 1. isPalindrome[i][j] will reuse the result of isPalindrome[i+1][j-1]

 2. f(i) will reuse the result of f(i+1), f(i+2)....
    if we find isPalindrome[i][j] == true, then we have to update f(i) = min (f(i), 1 + f(j+1))
    1 + f(j+1) means: we know we can cut at j | j+1, since i-j is palindrome, so add 1 to f(j+1)

 a b c b d d d
 0 1 2 3 4 5 6

 Assume we at b (i = 1)
 bc is not palindrome, go to next step
 bcb is palindrome, update f(1) = 1 + f(4)
 bcbd is not palindrome.......

 O(n * n) time complexity

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q132PalindromePartitioning.playground/Contents.swift