Edit distance stap voor stap
Invoegen, verwijderen en vervangen om te transformeren
Edit distance stap voor stap is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat bewerkingsafstand meet
Bewerkingsafstand is het kleinste aantal bewerkingen met afzonderlijke tekens om de ene tekenreeks in de andere te veranderen. Het geeft aan hoe verschillend twee woorden echt zijn.
De drie bewerkingen
Je mag per bewerking één teken invoegen, verwijderen of vervangen. In het standaardprobleem kost elke bewerking precies één.
Definieer de toestand
Laat dp[i][j] het aantal bewerkingen zijn om de eerste i tekens van A te veranderen in de eerste j tekens van B.
Overeenkomst kost niets
Als de huidige tekens al overeenkomen, is geen bewerking nodig. Je neemt de waarde op de diagonaal gewoon over.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Anders betaal je één
Als de tekens verschillen, neem je de goedkoopste buur en tel je één bewerking op. Dat minimum plus één dekt alle drie de bewerkingen.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Welke buur is welke
De cel erboven staat voor verwijderen, de cel links voor invoegen en de diagonaal voor vervangen. Het minimum kiest gewoon de goedkoopste.
Basisgevallen voor lege tekenreeksen
Om een tekenreeks met lengte i leeg te maken, zijn i verwijderingen nodig. Vul daarom de eerste rij en kolom met 0, 1, 2 enzovoort.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jBepaal de tabelgrootte
Gebruik een raster van n+1 bij m+1, zodat de lege voorvoegsels hun eigen rij en kolom krijgen. Deze opvulling houdt de lussen eenvoudig.
dp = [[0] * (m+1) for _ in range(n+1)]Vul in de juiste volgorde
Doorloop i en j vanaf 1. Elke cel hangt alleen af van al ingevulde buren boven, links en op de diagonaal.
for i in range(1, n+1):
for j in range(1, m+1):
...Lees de afstand
Het kleinste aantal bewerkingen komt in de hoek terecht. Je antwoord is dp[n][m] nadat de tabel compleet is.
distance = dp[n][m]Kosten en varianten
Dit kost O(n times m) tijd. In echte opdrachten kunnen bewerkingen verschillende kosten hebben, maar dezelfde recursie blijft werken.
Snelle controle
De tekens A[i-1] en B[j-1] verschillen. Welke recursie geeft de bewerkingsafstand?
Samenvatting: bewerkingsafstand
Bij een overeenkomst neem je de diagonaal over; bij een verschil neem je 1 plus het minimum van drie buren. Initialiseer de randen en lees dp[n][m] uit. ✏️
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Edit distance stap voor stap” gratis?
Ja — de volledige tekst van “Edit distance stap voor stap” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Edit distance stap voor stap”?
Invoegen, verwijderen en vervangen om te transformeren Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Edit distance stap voor stap”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Paden tellen in een raster
- Minimale padsom met obstakels
- Langste gemeenschappelijke subsequence
- Edit distance stap voor stap