Algorytmy i struktury danych · Senior · Pytanie 67 z 75
Jak w O(n) sprawdzić, czy dwa słowa różnią się o jedną edycję?
- 1Policzyć całą tabelę Levenshteina i sprawdzić, czy wynosi 1
- 2Posortować oba słowa i porównać wyniki
- ✓Poprawna odpowiedź: Dwa wskaźniki z dozwolonym jednym pominięciem lub różnicą
Wyjaśnienie
Jeśli długości różnią się o więcej niż jeden, odpowiedź brzmi nie. W przeciwnym razie przesuwaj wskaźniki razem i przy pierwszej różnicy pomiń znak w dłuższym słowie (lub w obu, gdy długości są równe). Pełne DP to O(n × m).