Edit distance trin for trin
Indsæt, slet og erstat for at transformere
Edit distance trin for trin er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Competitive Programming Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad redigeringsafstand måler
Redigeringsafstand er det mindste antal enkelttegnsændringer, der skal til for at omdanne én streng til en anden. Den viser, hvor forskellige to ord faktisk er.
De tre operationer
Du må indsætte, slette eller erstatte ét tegn pr. ændring. I standardproblemet koster hver operation præcis én.
Definér tilstanden
Lad dp[i][j] være antallet af ændringer for at omdanne de første i tegn af A til de første j tegn af B.
Gratis overensstemmelse
Hvis de aktuelle tegn allerede er ens, er der ikke brug for nogen ændring. Du fører blot værdien på diagonalen videre.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Ellers betaler du én
Når tegnene er forskellige, vælger du den billigste nabo og lægger én ændring til. Denne min plus én dækker alle tre operationer.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Hvilken nabo er hvad
Cellen ovenfor er en sletning, cellen til venstre er en indsættelse, og diagonalen er en erstatning. Min vælger blot den billigste.
Basistilfælde for tom streng
Det kræver i sletninger at omdanne en streng med længde i til en tom streng. Udfyld derfor den første række og kolonne 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] = jDimensionér tabellen
Brug et gitter på n+1 gange m+1, så de tomme præfikser får deres egen række og kolonne. Denne udfyldning holder løkkerne enkle.
dp = [[0] * (m+1) for _ in range(n+1)]Udfyld i rækkefølge
Gå gennem i og j fra 1 og opefter. Hver celle afhænger kun af allerede udfyldte naboer ovenfor, til venstre og på diagonalen.
for i in range(1, n+1):
for j in range(1, m+1):
...Læs afstanden
Det minimale antal ændringer ender i hjørnet. Dit svar er dp[n][m], når tabellen er færdig.
distance = dp[n][m]Omkostninger og varianter
Dette kræver O(n gange m) tid. I virkelige opgaver kan de forskellige operationer have forskellige omkostninger, men den samme rekurrens fungerer stadig.
Hurtigt tjek
Tegnene A[i-1] og B[j-1] er forskellige. Hvilken rekurrens giver redigeringsafstanden?
Opsummering: Redigeringsafstand
Ens tegn betyder, at diagonalen føres videre; forskellige tegn betyder 1 plus minimum af tre naboer. Initialisér kanterne, og læs dp[n][m]. ✏️
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Edit distance trin for trin” gratis?
Ja — hele teksten til “Edit distance trin for trin” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Competitive Programming Academy-kurset, skal du opgradere til CoddyKit PRO. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Edit distance trin for trin”?
Indsæt, slet og erstat for at transformere Du øver dig i Competitive Programming Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Competitive Programming Academy?
Der kræves ingen tidligere erfaring. Competitive Programming Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Edit distance trin for trin”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Competitive Programming Academy-lektion?
Ja. Alle Competitive Programming Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Stitælling i et gitter
- Mindste stisum med forhindringer
- Længste fælles delsekvens
- Edit distance trin for trin