LeetCode – Particionamiento Palindrome II (Java)

Dada una cadena s, la partición es tal que cada subcadena de la partición sea un palíndromo. Devuelva los cortes mínimos necesarios para un tabique palíndromo de s. Por ejemplo, dado s = «aab», devuelve 1 ya que la partición palíndromo [«aa»,»b»] podría producirse con 1 corte.

Análisis

Este problema es similar al particionamiento Palindrome. Puede resolverse de manera eficiente mediante el uso de programación dinámica. A diferencia del «Particionamiento Palindrome», necesitamos mantener dos matrices de caché, una rastrea la posición de la partición y la otra rastrea el número de corte mínimo.

Solución Java

public int minCut(String s) {
    int n = s.length();
 
	boolean dp[][] = new boolean[n][n];
	int cut[] = new int[n];
 
	for (int j = 0; j < n; j++) {
		cut[j] = j; //set maximum # of cut
		for (int i = 0; i <= j; i++) {
			if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1])) {
				dp[i][j] = true;
 
				// if need to cut, add 1 to the previous cut[i-1]
				if (i > 0){
					cut[j] = Math.min(cut[j], cut[i-1] + 1);
				}else{
				// if [0...j] is palindrome, no need to cut    
					cut[j] = 0; 
				}	
			}
		}
	}
 
	return cut[n-1];
}