[Leetcode] Palindrome Partitioning I and II

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

1. Return all possible palindrome partitioning of s.

For example, given s = "aab",

return [ ["aa","b"], ["a","a","b"] ]

2. Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Algorithm

For both problems, we can build an isPal table, where isPal[i][j] indicates whether s[i ... j] is a palindrome. This table can be built in O(n^2), using DP. 

The Problem 1 is a NP problem, since we need to consider all possible cutting position of string. There are O(2^(n-1)) solutions to be traversed, since we can cut or not cut at each gap. For example, 

s = "aaa", there are four solutions. These NP problems, like Combination-like problems, Sudoku solver problem have a similar solution.

In Problem 2, after building the isPal table, we can use DP to build another minCuts table. minCut[i] indicates the minimum number of cuts to partition s[0 ... i] to palindromes. 

                   minCuts[i] = min(minCuts[j]) + 1, where s[j .. i] is a palindrome and 0 <= j <= i.  

The running time is O(n^2), since both table can be built in O(n^2) time.

Note, don't think of dfs and bfs to make it complicated.  

Code