Editeringsavstånd steg för steg
Infoga, ta bort och ersätt för att omforma
Editeringsavstånd steg för steg är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad redigeringsavstånd mäter
Redigeringsavstånd är det minsta antalet enskilda teckenändringar som krävs för att omvandla en sträng till en annan. Det visar hur olika två ord faktiskt är.
De tre operationerna
Ni får infoga, ta bort eller ersätta ett tecken per ändring. I standardproblemet kostar varje operation exakt ett.
Definiera tillståndet
Låt dp[i][j] vara antalet ändringar för att omvandla de första i tecknen i A till de första j tecknen i B.
Kostnadsfri matchning
Om de aktuella tecknen redan matchar behövs ingen ändring. Ni för helt enkelt vidare värdet på diagonalen.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Annars betalar Ni ett
När tecknen skiljer sig väljer Ni den billigaste grannen och lägger till en ändring. min plus ett täcker alla tre operationerna.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Vilken granne betyder vad
Cellen ovanför betyder ta bort, cellen till vänster betyder infoga och diagonalen betyder ersätta. min väljer helt enkelt det billigaste alternativet.
Basfall för tomma strängar
Att omvandla en sträng med längden i till en tom sträng kräver i borttagningar. Fyll därför den första raden och kolumnen med 0, 1, 2 och så vidare.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jBestäm tabellens storlek
Använd ett n+1 by m+1-rutnät så att de tomma prefixen får en egen rad och kolumn. Denna utfyllnad håller looparna enkla.
dp = [[0] * (m+1) for _ in range(n+1)]Fyll i rätt ordning
Iterera över i och j från 1 och uppåt. Varje cell beror bara på redan ifyllda grannar ovanför, till vänster och på diagonalen.
for i in range(1, n+1):
for j in range(1, m+1):
...Läs av avståndet
Det minsta antalet ändringar hamnar i hörnet. Svaret är dp[n][m] när tabellen är komplett.
distance = dp[n][m]Kostnad och varianter
Detta körs på O(n gånger m) tid. I verkliga uppgifter kan olika operationer ha olika kostnader, men samma rekurrens fungerar fortfarande.
Snabb kontroll
Tecknen A[i-1] och B[j-1] skiljer sig. Vilken rekurrens ger redigeringsavståndet?
Sammanfattning: redigeringsavstånd
Matchning betyder att föra vidare diagonalen; vid skillnad betyder det 1 plus minimum av tre grannar. Initiera kanterna och läs av dp[n][m]. ✏️
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Editeringsavstånd steg för steg” gratis?
Ja – hela texten till ”Editeringsavstånd steg för steg” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Editeringsavstånd steg för steg”?
Infoga, ta bort och ersätt för att omforma Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Editeringsavstånd steg för steg”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Räkna vägar i ett rutnät
- Minsta vägsumma med hinder
- Längsta gemensamma delsekvens
- Editeringsavstånd steg för steg