Decode Ways og telling av stier
Løs decode-ways, med siffer-til-bokstav-avbildninger, som en Fibonacci-lignende DP, og tell deretter stier i en trapp med variable steglengder.
Decode Ways og telling av stier 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.
Problemet Decode Ways
Decode Ways (LeetCode 91) mapper en streng med sifre til bokstaver: 'A'=1, 'B'=2, ..., 'Z'=26. Gitt en kodet sifferstreng skal De telle antallet forskjellige måter den kan avkodes på. '12' kan for eksempel avkodes som 'AB' (1+2) eller 'L' (12), noe som gir 2 måter. '226' kan være 'BZ' (2+26), 'VF' (22+6) eller 'BBF' (2+2+6), noe som gir 3 måter. Innledende nuller gjør enkelte avkodninger ugyldige.
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3DP-formulering for Decode Ways
La dp[i] være antallet måter s[:i] kan dekodes på. Basistilfeller: dp[0] = 1 (tom streng, én måte), og dp[1] = 1 hvis s[0] != '0', ellers 0. Overgang: Hvis s[i-1] != '0', legges dp[i-1] til (dekoding med ett siffer). Hvis 10 ≤ int(s[i-2:i]) ≤ 26, legges dp[i-2] til (dekoding med to sifre). Dette er i hovedsak Fibonacci-mønsteret med gyldighetssjekker.
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0Fellen med innledende nuller
Den mest krevende delen av Decode Ways er å håndtere nuller. Et frittstående «0» kan ikke dekodes (ingen bokstav tilsvarer 0), så hvis s[i-1] == '0', skal dp[i-1] ikke legges til. En «0» som det andre sifferet er bare gyldig hvis tallet med to sifre er 10 eller 20. «30» eller «40» (og høyere) er ugyldige siden de overstiger 26. Kontroller alltid 10 ≤ two_digit ≤ 26, ikke bare two_digit ≤ 26.
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)Plassoptimalisert Decode Ways
I likhet med Fibonacci ser rekurrensen for antall dekodinger bare to posisjoner bakover, så O(n)-plassen kan reduseres til O(1) ved hjelp av to variabler. Bruk prev2 (to trinn tilbake) og prev1 (ett trinn tilbake). Beregn curr fra begge ved hvert trinn, og flytt deretter verdiene. Dette er identisk med Fibonacci → optimaliseringen med to variabler.
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0Telling av stier i en trapp
Climbing Stairs (LeetCode 70) spør: Hvor mange måter kan man gå opp n trappetrinn på hvis man kan ta 1 eller 2 trinn om gangen? Dette er nøyaktig Fibonacci-følgen: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Dette generaliseres når man kan ta opptil k trinn: ways(n) = sum(ways(n-1), ..., ways(n-k)).
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!Trappegang med variable trinn
Når man kan ta et vilkårlig antall trinn fra et gitt sett, for eksempel {1, 3, 5}, blir rekurrensen dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Bruk et glidende vindu med størrelse max(steps) for å utnytte minnet effektivt. Dette er tellevarianten av unbounded knapsack — hver trinnstørrelse kan brukes et vilkårlig antall ganger.
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)Trappegang med minimal kostnad
Min Cost Climbing Stairs (LeetCode 746) knytter en kostnad til hvert trinn og spør etter den laveste kostnaden for å nå toppen. Fra trinn i kan man hoppe til i+1 eller i+2. Rekurrensen er dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Man kan starte på trinn 0 eller trinn 1. Svaret er min(dp[n-1], dp[n-2]).
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6Decode Ways II: Siffer med jokertegn
Decode Ways II (LeetCode 639) introduserer jokertegnet «*», som kan representere et hvilket som helst siffer fra 1 til 9. Dette øker antallet gyldige dekodinger betraktelig. Et enkelt «*» bidrar med 9 muligheter (som hvilket som helst siffer fra 1 til 9). To «*» sammen kan danne 9×9 kombinasjoner med to sifre, men bare de som er ≤ 26, er gyldige (11–19 = 9 muligheter, 21–26 = 6 muligheter → 15 muligheter for «**»). Det kreves en grundig analyse av de ulike tilfellene.
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18Fibonacci-sammenhengen
Både Decode Ways og Climbing Stairs er i realiteten problemer fra Fibonacci-familien. All DP der dp[i] bare avhenger av dp[i-1] og dp[i-2], har Fibonacci-struktur og kan løses med O(1) plass. Gyldighetssjekkene (sifferet null, trinnstørrelser) avgjør hvilke overganger som er aktive, men endrer ikke den grunnleggende strukturen med to tidligere posisjoner. Å kjenne igjen denne familien med én gang er et verdifullt mønster for å jobbe raskt i tekniske intervjuer.
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89Telling av stier i et rutenett
Et beslektet telleproblem er følgende: Gitt et m×n-rutenett, hvor mange unike stier går fra øverst til venstre til nederst til høyre hvis man bare kan bevege seg mot høyre eller ned? Svaret er binomialkoeffisienten C(m+n-2, m-1). DP-løsningen fyller ut en 2D-tabell der dp[i][j] = dp[i-1][j] + dp[i][j-1]. Dette er en 2D-versjon av Fibonacci-trappen — hver celle er summen av cellen over og cellen til venstre.
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6Oppsummering av fallgruver i intervjuer
Vanlige fallgruver i Decode Ways: (1) Å glemme at «0» alene er ugyldig — kontroller alltid s[i-1] != '0' før dp[i-1] legges til. (2) Å bruke two_digit <= 26 uten å kontrollere two_digit >= 10 — «07» skal ikke dekodes som «G». (3) Å returnere dp[n-1] i stedet for dp[n] — tabellen er 1-indeksert, så dp[n] tilsvarer hele strengen. Kontroller alltid array-indeksene en ekstra gang når DP-tabellen har ett element mer enn inputen.
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)Hurtigsjekk
Test forståelsen av konseptene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte man at: Decode Ways følger en Fibonacci-lignende rekurrens med gyldighetsbetingelser for dekoding med ett siffer (ikke-null) og to sifre (10–26), Climbing Stairs og Min Cost Staircase er rene Fibonacci-varianter som kan løses med O(1) plass, og det å kjenne igjen Fibonacci-familien med to tidligere posisjoner sparer betydelig tid i intervjuer. Neste tema er 2D-DP med Unique Paths og Minimum Path Sum på rutenett.
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 «Decode Ways og telling av stier» gratis?
Ja – hele teksten i «Decode Ways og telling av stier» 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 «Decode Ways og telling av stier»?
Løs decode-ways, med siffer-til-bokstav-avbildninger, som en Fibonacci-lignende DP, og tell deretter stier i en trapp med variable steglengder. 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 «Decode Ways og telling av stier»?
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
- House Robber: ta-eller-hopp over-rekurrens
- Maksimumsdelarray og maksimumsproduktdelarray
- Word Break og segmentering av strenger
- Decode Ways og telling av stier