Algorithmen und Datenstrukturen · Senior · Frage 67 von 75
Wie prüft man in O(n), ob zwei Wörter eine Bearbeitung auseinanderliegen?
- 1Die volle Levenshtein-Tabelle berechnen und auf 1 prüfen
- 2Beide Wörter sortieren und die sortierten Ergebnisse vergleichen
- 3Zwei Zeiger, die einen einzigen Sprung oder eine Abweichung erlauben
Antwort zeigen
Richtige Antwort: Zwei Zeiger, die einen einzigen Sprung oder eine Abweichung erlauben
Erklärung
Unterscheiden sich die Längen um mehr als eins, lautet die Antwort nein. Sonst bewegt man die Zeiger gemeinsam und überspringt bei der ersten Abweichung ein Zeichen im längeren Wort (oder in beiden bei gleicher Länge). Die volle DP ist O(n × m).