Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Dynamic Programming Visualizer

Edit Distance (Levenshtein)

Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Table Size 0×0
Cells Filled 0
Status Ready
Uncomputed
Filling
Optimal path
0 / base case
Step Explanation

Select an algorithm and press Play to watch the table fill in.

—
Pseudocode 
 
 
 
 
  
 
 
Edit Distance (Levenshtein)
  
 
  Intermediate (3/5)
 
~1 hora   Minimum operations to transform strings  DP: insert, delete, replace  Relación con LCS  Weighted edit distance  
Prereqs: Programación dinámica, LCS  
 
Quick Reference
Edit Distance (Levenshtein)
Edit Distance (Levenshtein) measures how dissimilar two strings are by counting the minimum number of single-character edits — insertions, deletions, and substitutions — needed to turn one string into the other. dp[i][j] is the distance between the first i characters of a and the first j of b.

Difficulty: Intermediate (3/5)
dp
Complexity
Best Time
O(mn)
Average Time
O(mn)
Worst Time
O(mn)
Space
O(mn)
When to Use
Use for string similarity: spell checkers, DNA/protein sequence alignment, plagiarism detection, and fuzzy search ranking.
Pros
  • Exact minimum edit count via DP
  • Clear, symmetric recurrence
  • Foundation for many bioinformatics alignments
Cons
  • O(mn) time and space
  • Only counts edits — not a semantic similarity measure
  • Space can be reduced to O(min(m,n)) with two rows
History
The Levenshtein distance was introduced by the Soviet mathematician Vladimir Levenshtein in 1965. It is the most widely used edit-distance variant and is a staple of dynamic-programming courses, alongside LCS and knapsack.
 
 
Edit Distance (Levenshtein) calcula el mínimo número de operaciones (inserción, eliminación, reemplazo) para transformar una cadena s1 en otra s2. Es una métrica fundamental en procesamiento de texto, spell checkers, y bioinformática.


La versión estándar asigna costo 1 a cada operación. Existe una relación íntima con LCS: si todas las operaciones cuestan 1, edit_distance = len(s1) + len(s2) - 2 * LCS(s1, s2).


Cómo Funciona


    

  1. Inicializa tabla dp de tamaño (m+1) × (n+1) donde dp[i][j] = distancia entre s1[0..i) y s2[0..j).
    2. 

  2. Base: dp[i][0] = i (eliminar i chars), dp[0][j] = j (insertar j chars).
    3. 

  3. Recurre:

      

    • Si s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] (sin costo).
      • 

    • Si no: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (delete, insert, replace).
      • 

    

    4. 

  4. Resultado: dp[m][n].
    5. 



Idea Clave


La optimal substructure captura tres decisiones en cada celda (i,j):


    

  • Delete s1[i-1]: resolver s1[0..i-1) vs s2[0..j) → dp[i-1][j] + 1
    • 

  • Insert s2[j-1]: resolver s1[0..i) vs s2[0..j-1) → dp[i][j-1] + 1
    • 

  • Replace s1[i-1] con s2[j-1]: resolver el resto → dp[i-1][j-1] + 1
    • 



Si los caracteres coinciden, no necesitas operación: copias el costo del subproblema anterior.


Ejemplo Trabajado


s1 = "kitten", s2 = "sitting", m=6, n=7.


Tabla DP (primeras filas/columnas):


      Ø  s  i  t  t  i  n  g
Ø [ 0, 1, 2, 3, 4, 5, 6, 7 ]
k [ 1, 1, 2, 3, 4, 5, 6, 7 ]
i [ 2, 2, 1, 2, 3, 4, 5, 6 ]
t [ 3, 3, 2, 1, 2, 3, 4, 5 ]
t [ 4, 4, 3, 2, 1, 2, 3, 4 ]
e [ 5, 5, 4, 3, 2, 2, 3, 4 ]
n [ 6, 6, 5, 4, 3, 3, 2, 3 ]


Operaciones óptimas:


    

  1. k → s (replace, costo 1)
    2. 

  2. e → i (replace, costo 1)
    3. 

  3. Insert g al final (insert, costo 1)
    4. 



Resultado: dp[6][7] = 3.


Casos Extremos y Trampas


    

  • Strings idénticas — distancia 0.
    • 

  • Strings vacías — distancia = longitud de la otra.
    • 

  • Espacio — se reduce a O(min(m,n)) con dos filas.
    • 

  • LCS relación — solo para costos unitarios; con costos custom no aplica.
    • 



Comparación con Variantes































AlgoritmoOperacionesComplejidadUso
Levenshteinins/del/replO(mn)Spell check
Damerau-Levenshtein+ transposiciónO(mn)Spell check avanzado
LCSSolo match/replaceO(mn)Diff


Aplicaciones


    

  • Spell checkers — sugerir correcciones ortográficas
    • 

  • Bioinformática — alineamiento de secuencias de ADN
    • 

  • Diff de texto — mostrar cambios entre versiones
    • 

  • Procesamiento de lenguaje — normalización de texto, fuzzy search
    • 



Trayectoria de Práctica


    

  1. Implementa edit distance DP; traza kitten → sitting.
    2. 

  2. Optimiza a O(min(m,n)) espacio con dos filas.
    3. 

  3. Verifica la relación con LCS en un ejemplo.
    4. 

  4. Extiende a Damerau-Levenshtein: añade transposición.
    5. 

  5. Investiga weighted edit distance: ¿cómo cambiaría la DP?
    6.