LeetCode — Palindrome Partitioning II

Minimum number of cuts to ensure every sub string is a palindrome.

Example:

1. banana => b|anana
2. ababbbabbababa => ab|abba|bb|ababa

Please try on your own before reading on.

We will try to get to the solution via…

So at minCuts[3], the value at minCuts[3] refers to the minimum number of cuts to form palindromes for the string “bana” and in this case it is: 1 (after ‘b’). So minCuts[length -1] refers to the minimum cuts to form palindromes for “banana”.

minCuts[0]: “b” : 0 : ‘b’ is a palindrome in itself so zero cuts.

minCuts[1]: “ba” : 1 : “ba” is not a palindrome but ‘b’ is, so we add a 1 to minCuts[0].

minCuts[2]: “ban” : 2 : “ban” is not a palindrome so we add a 1 to minCuts[1]. That would give us the minimum.

You thought you saw a pattern… but things will get interesting…

minCuts[3]: “bana” : 1 : We can’t just add a 1 to minCuts[2]. “ana” is a palindrome so adding…