DP #24. Palindrome Partition. - mbhushan/dynpro GitHub Wiki

(24). Palindrome Partition.

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

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.

Formula:

if (isPalindrome(S[i...j]) {
    T[i][j] = 0;
} else {
    T[i][j] = Min (T[i][k] + T[k+1][j]) //for i <= k < j
}

		0	1	2	3	4
		a	x	y	x	b
0	a	0	1	2	1	2 (ans)
1	x		0	1	0	1
2	y			0	1	2
3	x				0	1
4	b					0

	public int palindromicPartition(char [] input) {
		int size = input.length;

		int [][] T = new int[size][size];

		for (int i=0; i<size; i++) {
			Arrays.fill(T[i], Integer.MAX_VALUE);
			T[i][i] = 0;
		}
		
		for (int len=1; len<=size; len++) {
			for (int i=0; i<size-len+1; i++) {
				int j = i + len - 1;
				if (isPalindrome(input, i, j)) {
					T[i][j] = 0;
					continue;
				}
				int val = Integer.MAX_VALUE;
				for (int k=i+1; k<=j; k++) {
					val = Math.min(val, 1 + (T[i][k-1] + T[k][j]));
				}
				T[i][j] = val;
			}
		}

[Palindrome Partition] (https://github.com/mbhushan/dynpro/blob/master/DP_PalindromicPartition/src/PalindromicPartition.java)

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)