Comments

• 
  

  1

  

  Ailema  commented on March 2, 2025, 12:38 a.m.

  No lo digo por nada pero podrían optar por poner el caso de prueba de acuerdo con el ejemplo; me explico; en el ejemplo del problema utilizan LOVE y MOVIE y en el caso de prueba son las mismas palabras pero en español. Y lo comento porque puede ser confuso para alguien con poca experiencia y poco conocimiento de inglés.

• 
  

  0

  

  Marco_Escandon  commented on March 2, 2025, 12:52 a.m. ← edited →

  Si, deberían ser las palabras en inglés un error de traducción. Será arreglado pronto. La respuesta al caso de ejemplo se basa en las palabras en inglés

• 
  

  -4

  

  Diego_Dario  commented on March 1, 2025, 10:47 p.m. ← edited →

  Editorial

  Este es un problema clásico llamado edit distance, que mide cuántas operaciones mínimas se necesitan para convertir una cadena a en otra cadena b.

  Definimos dp[i][k] como el mínimo número de movimientos para transformar los primeros i caracteres de a en los primeros k caracteres de b.

  Opciones para transformar a[i] en b[k] Al calcular dp[i][k], hay cuatro casos posibles según la última operación realizada:

  1️⃣ Eliminar el último carácter de a.

  Eliminamos a[i-1] Nos queda transformar a[i-1] en b[k] Costo: 1 + dp[i-1][k]

  2️⃣ Agregar un carácter al final de a.

  Añadimos b[k-1] al final de a[i] Nos queda transformar a[i] en b[k-1] Costo: 1 + dp[i][k-1]

  3️⃣ Reemplazar un carácter de a.

  Reemplazamos a[i-1] por b[k-1] Nos queda transformar a[i-1] en b[k-1] Costo: 1 + dp[i-1][k-1]

  4️⃣ No hacer nada (si los caracteres ya coinciden).

  Si a[i-1] == b[k-1], no necesitamos cambiar ese carácter Nos queda transformar a[i-1] en b[k-1] Costo: dp[i-1][k-1] Complejidad del Algoritmo El algoritmo tiene una complejidad de: O(∣a∣⋅∣b∣) Esto significa que el tiempo de ejecución crece proporcionalmente al producto de las longitudes de a y b.

  Código de Ejemplo

  *Copiar este código es una infracción baneable

  #include <bits/stdc++.h>
  using namespace std;
  
  int main() {
    string a, b;
    cin >> a >> b;
    int na = a.size(), nb = b.size();
    vector<vector<int>> dp(na+1, vector<int>(nb+1,1e9));
    dp[0][0] = 0;
    for (int i = 0; i <= na; i++) {
      for (int j = 0; j <= nb; j++) {
        if (i) {
      dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
        }
        if (j) {
      dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
        }
        if (i && j) {
      dp[i][j] = min(dp[i][j], dp[i-1][j-1]+(a[i-1] != b[j-1]));
        }
      }
    }
    cout << dp[na][nb] << endl;
  }