Programación DinámicaIntermediate

Distancia de Edición (Levenshtein)

Algoritmo de programación dinámica que calcula el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones, sustituciones) requeridas para transformar una cadena en otra. Fundamental en corrección ortográfica, alineación de secuencias de ADN y procesamiento de lenguaje natural.

#dynamic-programming#strings#levenshtein#spell-check

Complexity Analysis

Time (Average)

O(m × n)

Expected case performance

Space

O(m × n)

Memory requirements

Time (Best)

O(m × n)

Best case performance

Time (Worst)

O(m × n)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 15•Section 15.4

String 1 (Source)

String 2 (Target)

Example String Pairs:

How it works

• Minimum edits to transform string1 to string2
• Operations: insert, delete, replace
• Dynamic programming approach
• O(m × n) time and space complexity
• Also known as Levenshtein distance

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Programación Dinámica

Multiplicación de Cadenas de Matrices

Advanced

Encuentra la forma óptima de colocar paréntesis en una cadena de matrices para minimizar el número de multiplicaciones escalares. Problema clásico de programación dinámica del Capítulo 15 de CLRS.

O(n³)

O(n²)

dynamic-programmingoptimization

Start Learning

Fibonacci (Programación Dinámica)

Beginner

Calcula números de Fibonacci eficientemente usando programación dinámica para evitar cálculos redundantes. Demuestra el poder de la memoización al transformar una solución recursiva de tiempo exponencial en un algoritmo de tiempo lineal. Una introducción clásica a los conceptos de programación dinámica.

O(n)

dynamic-programmingmemoization

Start Learning

Subsecuencia Común más Larga (LCS)

Intermediate

Encuentra la subsecuencia más larga presente en dos secuencias en el mismo orden. Usa programación dinámica para construir una tabla de soluciones. Las aplicaciones incluyen alineación de secuencias de ADN, herramientas de diferencia de archivos (diff) y detección de plagio.

O(m × n)

dynamic-programmingstrings

Start Learning

Back to Programación Dinámica