Dynamische ProgrammierungIntermediate
Editierdistanz (Levenshtein)
Dynamischer Programmieralgorithmus, der die minimale Anzahl von Einzelzeichen-Bearbeitungen (Einfugungen, Loschungen, Ersetzungen) berechnet, die erforderlich sind, um einen String in einen anderen zu transformieren. Fundamental in Rechtschreibprufung, DNA-Sequenzabgleich und naturlicher Sprachverarbeitung.
#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