Decode Ways och räkning av vägar
Lös decode-ways, där siffror mappas till bokstäver, som en Fibonacci-liknande DP och räkna sedan vägar i en trappa med varierande steglängder.
Decode Ways och räkning av vägar är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 4 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Problemet Decode Ways
Decode Ways (LeetCode 91) mappar en sträng med siffror till bokstäver: 'A'=1, 'B'=2, ..., 'Z'=26. Givet en kodad siffersträng ska ni räkna antalet olika sätt att avkoda den. Till exempel kan '12' avkodas som 'AB' (1+2) eller 'L' (12), vilket ger 2 sätt. '226' kan vara 'BZ' (2+26), 'VF' (22+6) eller 'BBF' (2+2+6), vilket ger 3 sätt. Inledande nollor gör vissa avkodningar ogiltiga.
# 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 för Decode Ways
Låt dp[i] vara antalet sätt att avkoda s[:i]. Basfall: dp[0] = 1 (den tomma strängen kan avkodas på ett sätt), och dp[1] = 1 om s[0] != '0', annars 0. Övergång: om s[i-1] != '0' lägger man till dp[i-1] (avkodning med en siffra). Om 10 ≤ int(s[i-2:i]) ≤ 26 lägger man till dp[i-2] (avkodning med två siffror). Detta följer i praktiken Fibonacci-mönstret med giltighetskontroller.
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')) # 0Fällan med inledande nollor
Det mest utmanande i Decode Ways är att hantera nollor. En fristående '0' kan inte avkodas (ingen bokstav motsvarar 0), så om s[i-1] == '0' ska man inte lägga till dp[i-1]. En '0' som andra siffra är bara giltig om det tvåsiffriga talet är 10 eller 20. '30' eller '40' (och högre tal) är ogiltiga eftersom de överstiger 26. Kontrollera alltid 10 ≤ two_digit ≤ 26, inte bara 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)Minnesoptimerad avkodning med Decode Ways
Precis som för Fibonacci tittar rekurrensen för antalet avkodningar bara två positioner bakåt, så minnesåtgången kan minskas från O(n) till O(1) med hjälp av två variabler. Använd prev2 (två steg bakåt) och prev1 (ett steg bakåt). Beräkna curr från båda vid varje steg och flytta sedan variablerna ett steg framåt. Detta är samma optimering med två variabler som för Fibonacci.
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')) # 0Räkna vägar i en trappa
Climbing Stairs (LeetCode 70) frågar hur många sätt man kan ta sig uppför n trappsteg om man kan ta 1 eller 2 steg åt gången. Detta är exakt Fibonacciföljden: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Det generaliseras när man kan ta upp till k steg: 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!Trappsteg med varierande steglängder
När man får ta valfritt antal steg från en given uppsättning (t.ex. {1, 3, 5}) blir rekurrensen dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Använd ett glidande fönster med storleken max(steps) för effektiv minnesanvändning. Detta är räkningsvarianten av unbounded knapsack — varje steglängd kan användas hur många gånger som helst.
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...)Minsta kostnad för att klättra i trappan
Min Cost Climbing Stairs (LeetCode 746) tilldelar varje trappsteg en kostnad och frågar efter den minsta kostnaden för att nå toppen. Från steg i kan man hoppa till i+1 eller i+2. Rekurrensen är dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Man kan börja från steg 0 eller steg 1. Svaret är 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: jokertecken
Decode Ways II (LeetCode 639) introducerar jokertecknet '*' som kan representera valfri siffra från 1 till 9. Detta ökar antalet giltiga avkodningar kraftigt. En ensam '*' bidrar med 9 sätt (en för varje siffra från 1 till 9). Två '*' tillsammans kan bilda 9×9 tvåsiffriga kombinationer, men bara de som är ≤ 26 är giltiga (11–19 = 9 sätt, 21–26 = 6 sätt → 15 sätt för '**'). Noggrann fallanalys krävs.
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-sambandet
Både Decode Ways och Climbing Stairs är i grunden problem i Fibonacci-familjen. All DP där dp[i] bara beror på dp[i-1] och dp[i-2] har Fibonacci-struktur och kan lösas med O(1) minne. Giltighetskontrollerna (nollsiffror och steglängder) avgör vilka övergångar som är aktiva, men ändrar inte den grundläggande strukturen med beroenden två steg bakåt. Att känna igen denna familj direkt är ett värdefullt mönster för att arbeta snabbt under 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) # 89Räkna vägar i ett rutnät
Ett närliggande räkningsproblem är följande: givet ett m×n-rutnät, hur många unika vägar går från det övre vänstra hörnet till det nedre högra om man bara får röra sig åt höger eller nedåt? Svaret är binomialkoefficienten C(m+n-2, m-1). DP-lösningen fyller i en tvådimensionell tabell där dp[i][j] = dp[i-1][j] + dp[i][j-1]. Detta är en tvådimensionell version av Fibonacci-trappan — varje cell är summan av cellen ovanför och cellen till vänster.
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)) # 6Sammanfattning av vanliga intervjufällor
Vanliga fallgropar i Decode Ways: (1) Att glömma att '0' ensam är ogiltig — kontrollera alltid s[i-1] != '0' innan dp[i-1] läggs till. (2) Att använda two_digit <= 26 utan att kontrollera two_digit >= 10 — '07' ska inte avkodas som 'G'. (3) Att returnera dp[n-1] i stället för dp[n] — tabellen är 1-indexerad, så dp[n] motsvarar hela strängen. Kontrollera alltid arrayindex noggrant när DP-tabellen har ett element mer än indata.
# 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)Snabbkontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen har ni lärt er att Decode Ways följer en Fibonacci-liknande rekurrens med giltighetskontroller för avkodningar med en siffra (icke-noll) och två siffror (10–26), att Climbing Stairs och Min Cost Staircase är rena Fibonacci-varianter som kan lösas med O(1) minne, samt att igenkänning av Fibonacci-familjen med beroenden två steg bakåt sparar betydande tid under intervjuer. Nästa del handlar om tvådimensionell DP med Unique Paths och Minimum Path Sum i rutnät.
Lär dig Python 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
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Decode Ways och räkning av vägar” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Decode Ways och räkning av vägar”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Decode Ways och räkning av vägar”?
Lös decode-ways, där siffror mappas till bokstäver, som en Fibonacci-liknande DP och räkna sedan vägar i en trappa med varierande steglängder. Ni övar på DSA Interview Prep 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 DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep 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 ”Decode Ways och räkning av vägar”?
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 DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-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
- House Robber: rekurrens för ta eller hoppa över
- Delarray med maximal summa och maximal produkt
- Word Break och segmentering av strängar
- Decode Ways och räkning av vägar