Algorithmen und Datenstrukturen · Middle · Frage 46 von 75
Was misst die Levenshtein-(Edit-)Distanz?
- 1Den Längenunterschied zwischen den beiden Strings
- 2Die Zahl der Positionen, an denen sich zwei gleich lange Strings unterscheiden
- 3Minimum an Einfügungen, Löschungen und Ersetzungen, um einen in den anderen umzuwandeln
Antwort zeigen
Richtige Antwort: Minimum an Einfügungen, Löschungen und Ersetzungen, um einen in den anderen umzuwandeln
Erklärung
Man berechnet sie mit einer DP-Tabelle in O(n × m), und sie treibt Rechtschreibprüfungen und Vorschläge „meinten Sie...?“ an. Abweichende Positionen in gleich langen Strings zu zählen ist die Hamming-Distanz.