Programmation dynamiqueIntermediate
Distance d'édition (Levenshtein)
Algorithme de programmation dynamique qui calcule le nombre minimum d'éditions de caractères uniques (insertions, suppressions, substitutions) nécessaires pour transformer une chaîne en une autre. Fondamental dans la correction orthographique, l'alignement de séquences ADN et le traitement du langage naturel.
#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
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
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation