String dada str . Puede eliminar solo algunos caracteres contiguos si todos los caracteres son iguales en una sola operación. La tarea es encontrar el número mínimo de operaciones requeridas para eliminar completamente la string.
Ejemplos:
Entrada: str = “abcddcba”
Salida: 4
Eliminar dd, luego la string es “abccba”
Eliminar cc, luego la string es “abba”
Eliminar bb, luego la string es “aa”
Eliminar aa, luego la string es nula.
Entrada: str = “abc”
Salida: 3
Enfoque: El problema se puede resolver utilizando <a href=”http://wwl<=iDynamic Programming y la técnica Divide and Conquer .
Sea dp[l][r] la respuesta para la substring s[l, l+1, l+2, …r]. Entonces tenemos dos casos:
- La primera letra de la substring se elimina por separado del resto, luego dp[l][r] = 1 + dp[l+1][r] .
- La primera letra de la substring se elimina junto con alguna otra letra (ambas letras deben ser iguales), luego dp[l][r] = dp[l+1][i-1] + dp[i][r ] , dado que l ≤ yo ≤ r y s[i] = s[l] .
Los siguientes dos casos se pueden llamar recursivamente junto con la memorización para evitar llamadas de funciones repetitivas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
// Function to return the minimum number of
// delete operations
int findMinimumDeletion(int l, int r, int dp[N][N], string s)
{
if (l > r)
return 0;
if (l == r)
return 1;
if (dp[l][r] != -1)
return dp[l][r];
// When a single character is deleted
int res = 1 + findMinimumDeletion(l + 1, r, dp, s);
// When a group of consecutive characters
// are deleted if any of them matches
for (int i = l + 1; i <= r; ++i) {
// When both the characters are same then
// delete the letters in between them
if (s[l] == s[i])
res = min(res, findMinimumDeletion(l + 1, i - 1, dp, s)
+ findMinimumDeletion(i, r, dp, s));
}
// Memoize
return dp[l][r] = res;
}
// Driver code
int main()
{
string s = "abcddcba";
int n = s.length();
int dp[N][N];
memset(dp, -1, sizeof dp);
cout << findMinimumDeletion(0, n - 1, dp, s);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static int N = 10;
// Function to return the minimum number of
// delete operations
static int findMinimumDeletion(int l, int r,
int dp[][], String s)
{
if (l > r)
{
return 0;
}
if (l == r)
{
return 1;
}
if (dp[l][r] != -1)
{
return dp[l][r];
}
// When a single character is deleted
int res = 1 + findMinimumDeletion(l + 1, r, dp, s);
// When a group of consecutive characters
// are deleted if any of them matches
for (int i = l + 1; i <= r; ++i)
{
// When both the characters are same then
// delete the letters in between them
if (s.charAt(l) == s.charAt(i))
{
res = Math.min(res, findMinimumDeletion(l + 1, i - 1, dp, s)
+ findMinimumDeletion(i, r, dp, s));
}
}
// Memoize
return dp[l][r] = res;
}
// Driver code
public static void main(String[] args)
{
String s = "abcddcba";
int n = s.length();
int dp[][] = new int[N][N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
dp[i][j] = -1;
}
}
System.out.println(findMinimumDeletion(0, n - 1, dp, s));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the minimum # number of delete operations def findMinimumDeletion(l, r, dp, s): if l > r: return 0 if l == r: return 1 if dp[l][r] != -1: return dp[l][r] # When a single character is deleted res = 1 + findMinimumDeletion(l + 1, r, dp, s) # When a group of consecutive characters # are deleted if any of them matches for i in range(l + 1, r + 1): # When both the characters are same then # delete the letters in between them if s[l] == s[i]: res = min(res, findMinimumDeletion(l + 1, i - 1, dp, s) + findMinimumDeletion(i, r, dp, s)) # Memoize dp[l][r] = res return res # Driver code if __name__ == "__main__": s = "abcddcba" n = len(s) N = 10 dp = [[-1 for i in range(N)] for j in range(N)] print(findMinimumDeletion(0, n - 1, dp, s)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
static int N = 10;
// Function to return the minimum number of
// delete operations
static int findMinimumDeletion(int l, int r,
int [,]dp, String s)
{
if (l > r)
{
return 0;
}
if (l == r)
{
return 1;
}
if (dp[l, r] != -1)
{
return dp[l, r];
}
// When a single character is deleted
int res = 1 + findMinimumDeletion(l + 1, r, dp, s);
// When a group of consecutive characters
// are deleted if any of them matches
for (int i = l + 1; i <= r; ++i)
{
// When both the characters are same then
// delete the letters in between them
if (s[l] == s[i])
{
res = Math.Min(res, findMinimumDeletion(l + 1, i - 1, dp, s)
+ findMinimumDeletion(i, r, dp, s));
}
}
// Memoize
return dp[l,r] = res;
}
// Driver code
public static void Main(String[] args)
{
String s = "abcddcba";
int n = s.Length;
int [,]dp = new int[N, N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
dp[i, j] = -1;
}
}
Console.WriteLine(findMinimumDeletion(0, n - 1, dp, s));
}
}
// This code has been contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
$GLOBALS['N'] = 10;
// Function to return the minimum
// number of delete operations
function findMinimumDeletion($l, $r, $dp, $s)
{
if ($l > $r)
return 0;
if ($l == $r)
return 1;
if ($dp[$l][$r] != -1)
return $dp[$l][$r];
// When a single character is deleted
$res = 1 + findMinimumDeletion($l + 1, $r,
$dp, $s);
// When a group of consecutive characters
// are deleted if any of them matches
for ($i = $l + 1; $i <= $r; ++$i)
{
// When both the characters are same then
// delete the letters in between them
if ($s[$l] == $s[$i])
$res = min($res, findMinimumDeletion($l + 1, $i - 1, $dp, $s) +
findMinimumDeletion($i, $r, $dp, $s));
}
// Memoize
return $dp[$l][$r] = $res;
}
// Driver code
$s = "abcddcba";
$n = strlen($s);
$dp = array(array());
for($i = 0; $i < $GLOBALS['N']; $i++)
for($j = 0; $j < $GLOBALS['N']; $j++)
$dp[$i][$j] = -1 ;
echo findMinimumDeletion(0, $n - 1, $dp, $s);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of the approach
var N = 10;
// Function to return the minimum number of
// delete operations
function findMinimumDeletion(l, r, dp, s)
{
if (l > r)
return 0;
if (l == r)
return 1;
if (dp[l][r] != -1)
return dp[l][r];
// When a single character is deleted
var res = 1 + findMinimumDeletion(l + 1, r, dp, s);
// When a group of consecutive characters
// are deleted if any of them matches
for (var i = l + 1; i <= r; ++i) {
// When both the characters are same then
// delete the letters in between them
if (s[l] == s[i])
res =
Math.min(res, findMinimumDeletion(l + 1, i - 1, dp, s)
+ findMinimumDeletion(i, r, dp, s));
}
// Memoize
return dp[l][r] = res;
}
// Driver code
var s = "abcddcba";
var n = s.length;
var dp = Array.from(Array(N), ()=> Array(N).fill(-1));
document.write( findMinimumDeletion(0, n - 1, dp, s));
</script>
Producción:
4
Complejidad de tiempo: O (N * N), ya que estamos usando un ciclo para atravesar N veces y en cada recorrido estamos llamando recursivamente a la función que costará O (N) tiempo. Donde N es la longitud de la string.
Espacio auxiliar: O(N*N), ya que estamos usando espacio adicional para la array dp. Donde N es la longitud de la string.