Redigeringsavstand steg for steg
Sett inn, slett og erstatt for å transformere
Redigeringsavstand steg for steg er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva redigeringsavstand måler
Redigeringsavstand er det minste antallet enkelttegnsoperasjoner som trengs for å gjøre én streng om til en annen. Den viser hvor forskjellige to ord faktisk er.
De tre operasjonene
Du kan sette inn, slette eller erstatte ett tegn per operasjon. I standardproblemet koster hver operasjon nøyaktig én.
Definer tilstanden
La dp[i][j] være antallet operasjoner for å endre de første i tegnene i A til de første j tegnene i B.
Kostnadsfritt samsvar
Hvis de gjeldende tegnene allerede samsvarer, trengs ingen operasjon. Du fører ganske enkelt den diagonale verdien videre.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Ellers betaler Du én
Når tegnene er forskjellige, velger Du den billigste naboen og legger til én operasjon. Dette min pluss én dekker alle tre operasjonene.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Hvilken nabo er hva
Cellen over betyr sletting, cellen til venstre betyr innsetting, og diagonalen betyr erstatning. min velger ganske enkelt det billigste alternativet.
Grunntilfeller for tom streng
Å gjøre en streng med lengde i om til en tom streng krever i slettinger. Fyll derfor den første raden og kolonnen med 0, 1, 2 og så videre.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jBestem tabellstørrelsen
Bruk et rutenett på n+1 ganger m+1, slik at de tomme prefiksene får sin egen rad og kolonne. Denne utfyllingen holder løkkene enkle.
dp = [[0] * (m+1) for _ in range(n+1)]Fyll ut i riktig rekkefølge
Gå gjennom i og j oppover fra 1. Hver celle avhenger bare av allerede utfylte naboer over, til venstre og diagonalt.
for i in range(1, n+1):
for j in range(1, m+1):
...Les av avstanden
Det minste antallet operasjoner ender opp i hjørnet. Svaret er dp[n][m] når tabellen er ferdig.
distance = dp[n][m]Kostnad og varianter
Dette tar O(n ganger m) tid. I virkelige oppgaver kan hver operasjon ha ulik kostnad, men den samme rekurrensen fungerer fortsatt.
Hurtigsjekk
Tegnene A[i-1] og B[j-1] er forskjellige. Hvilken rekurrens gir redigeringsavstanden?
Oppsummering: Redigeringsavstand
Samsvar betyr at Du fører diagonalen videre; ulikhet betyr 1 pluss minimum av tre naboer. Initialiser kantene og les av dp[n][m]. ✏️
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Redigeringsavstand steg for steg» gratis?
Ja – hele teksten i «Redigeringsavstand steg for steg» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Redigeringsavstand steg for steg»?
Sett inn, slett og erstatt for å transformere Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Redigeringsavstand steg for steg»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Tell stier i et rutenett
- Minste stisum med hindringer
- Lengste felles delsekvens
- Redigeringsavstand steg for steg