0Pricing
DSA Interview Prep · Lektion

Decode Ways und Pfade zählen

Lösen Sie decode-ways (Ziffer-zu-Buchstabe-Zuordnungen) mit einer Fibonacci-ähnlichen DP und zählen Sie anschließend Pfade auf einer Treppe mit variablen Schrittgrößen.

Decode Ways und Pfade zählen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Das Decode-Ways-Problem

Decode Ways (LeetCode 91) ordnet eine Ziffernfolge Buchstaben zu: 'A'=1, 'B'=2, ..., 'Z'=26. Bei einer codierten Ziffernfolge sollen Sie die Anzahl der verschiedenen Möglichkeiten zur Decodierung ermitteln. Beispielsweise kann '12' als 'AB' (1+2) oder als 'L' (12) decodiert werden, also auf 2 Arten. '226' kann 'BZ' (2+26), 'VF' (22+6) oder 'BBF' (2+2+6) ergeben, also auf 3 Arten. Führende Nullen machen einige Decodierungen ungültig.

# 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: 3

DP-Formulierung für Decode Ways

Setzen Sie dp[i] als die Anzahl der Möglichkeiten fest, s[:i] zu dekodieren. Anfangsfälle: dp[0] = 1 (leere Zeichenkette, eine Möglichkeit) und dp[1] = 1, wenn s[0] != '0', andernfalls 0. Übergang: Wenn s[i-1] != '0', addieren Sie dp[i-1] (Dekodierung einer einzelnen Ziffer). Wenn 10 ≤ int(s[i-2:i]) ≤ 26, addieren Sie dp[i-2] (Dekodierung von zwei Ziffern). Im Wesentlichen handelt es sich um das Fibonacci-Muster mit Gültigkeitsprüfungen.

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'))   # 0

Die Falle der führenden Null

Der schwierigste Teil von Decode Ways ist der Umgang mit Nullen. Eine alleinstehende „0“ kann nicht dekodiert werden (keinem Buchstaben ist 0 zugeordnet). Wenn also s[i-1] == '0', dürfen Sie dp[i-1] nicht addieren. Eine „0“ als zweite Ziffer ist nur gültig, wenn die zweistellige Zahl 10 oder 20 ist. „30“ oder „40“ (und größere Zahlen) sind ungültig, da sie 26 überschreiten. Prüfen Sie stets 10 ≤ two_digit ≤ 26, nicht nur 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)

Speicheroptimierte Lösung für Decode Ways

Wie bei Fibonacci betrachtet die Rekurrenz für die Anzahl der Dekodierungen nur die beiden vorherigen Positionen. Daher können Sie den Speicherbedarf mit zwei Variablen von O(n) auf O(1) reduzieren. Verwenden Sie prev2 (zwei Schritte zurück) und prev1 (einen Schritt zurück). Berechnen Sie in jedem Schritt curr aus beiden Werten und verschieben Sie sie anschließend. Dies entspricht exakt der Fibonacci-Optimierung auf zwei Variablen.

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'))     # 0

Pfade in einer Treppe zählen

Climbing Stairs (LeetCode 70) stellt die Frage: Auf wie viele Arten können Sie n Stufen hinaufsteigen, wenn Sie jeweils 1 oder 2 Stufen nehmen dürfen? Das ist genau die Fibonacci-Folge: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Das lässt sich verallgemeinern, wenn Sie bis zu k Stufen auf einmal nehmen dürfen: 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!

Treppensteigen mit variabler Schrittweite

Wenn Sie eine beliebige Anzahl von Stufen aus einer vorgegebenen Menge nehmen dürfen (z. B. {1, 3, 5}), lautet die Rekurrenz dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Verwenden Sie aus Gründen der Speichereffizienz ein gleitendes Fenster der Größe max(steps). Dies ist die Zählvariante des unbeschränkten Rucksackproblems — jede Schrittweite kann beliebig oft verwendet werden.

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...)

Minimum Cost Climbing Stairs

Min Cost Climbing Stairs (LeetCode 746) ordnet jeder Stufe Kosten zu und fragt nach den minimalen Kosten, um die oberste Stufe zu erreichen. Von Stufe i aus können Sie zu i+1 oder i+2 springen. Die Rekurrenz lautet dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Sie können bei Stufe 0 oder Stufe 1 beginnen. Die Antwort ist 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]))  # 6

Decode Ways II: Jokerziffer

Decode Ways II (LeetCode 639) führt das Jokerzeichen „*“ ein, das jede Ziffer von 1 bis 9 darstellen kann. Dadurch steigt die Anzahl der gültigen Dekodierungen erheblich. Ein einzelnes „*“ trägt 9 Möglichkeiten bei (für jede Ziffer von 1 bis 9). Zwei „*“ können zusammen 9×9 zweistellige Kombinationen bilden, aber nur die Kombinationen ≤ 26 sind gültig (11–19 = 9 Möglichkeiten, 21–26 = 6 Möglichkeiten → 15 Möglichkeiten für „**“). Eine sorgfältige Fallunterscheidung ist erforderlich.

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*'))  # 18

Die Verbindung zu Fibonacci

Sowohl Decode Ways als auch Climbing Stairs sind im Grunde Probleme aus der Fibonacci-Familie. Jede DP, bei der dp[i] nur von dp[i-1] und dp[i-2] abhängt, hat eine Fibonacci-Struktur und lässt sich mit O(1) Speicher lösen. Die Gültigkeitsprüfungen (Nullziffern, Schrittweiten) bestimmen, welche Übergänge aktiv sind, ändern aber nichts an der grundlegenden Struktur mit zwei Rückblicken. Diese Familie auf Anhieb zu erkennen, ist ein wertvolles Muster, um in Interviews Zeit zu sparen.

# 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)  # 89

Pfade in einem Gitter zählen

Ein verwandtes Zählproblem: Gegeben sei ein m×n-Gitter. Wie viele eindeutige Pfade führen von der oberen linken zur unteren rechten Ecke, wenn Sie sich nur nach rechts oder unten bewegen dürfen? Die Antwort ist der Binomialkoeffizient C(m+n-2, m-1). Die DP-Lösung füllt eine zweidimensionale Tabelle, in der dp[i][j] = dp[i-1][j] + dp[i][j-1] gilt. Dies ist eine zweidimensionale Version der Fibonacci-Treppe — jede Zelle ist die Summe der Zelle darüber und der Zelle links daneben.

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))         # 6

Zusammenfassung typischer Fehler im Interview

Typische Fehler bei Decode Ways: (1) Zu vergessen, dass „0“ allein ungültig ist — prüfen Sie stets s[i-1] != '0', bevor Sie dp[i-1] addieren. (2) two_digit <= 26 zu verwenden, ohne two_digit >= 10 zu prüfen — „07“ sollte nicht als „G“ dekodiert werden. (3) dp[n-1] statt dp[n] zurückzugeben — die Tabelle ist 1-basiert, daher entspricht dp[n] der vollständigen Zeichenkette. Überprüfen Sie Array-Indizes stets doppelt, wenn Ihre DP-Tabelle ein Element mehr als die Eingabe enthält.

# 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)

Schnelltest

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

Zusammenfassung der Lektion

In dieser Lektion haben Sie gelernt: Decode Ways folgt einer Fibonacci-ähnlichen Rekurrenz mit Gültigkeitsbedingungen für Dekodierungen mit einer einzelnen Ziffer (ungleich null) und mit zwei Ziffern (10–26), Climbing Stairs und Min Cost Staircase sind reine Fibonacci-Varianten, die sich mit O(1) Speicher lösen lassen, und das Erkennen der Fibonacci-Familie mit zwei Rückblicken spart in Interviews erheblich Zeit. Als Nächstes untersuchen wir die 2D-DP mit Unique Paths und Minimum Path Sum auf Gittern.

Häufig gestellte Fragen

Ist die Lektion „Decode Ways und Pfade zählen“ kostenlos?

Ja — der vollständige Text von „Decode Ways und Pfade zählen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Decode Ways und Pfade zählen“?

Lösen Sie decode-ways (Ziffer-zu-Buchstabe-Zuordnungen) mit einer Fibonacci-ähnlichen DP und zählen Sie anschließend Pfade auf einer Treppe mit variablen Schrittgrößen. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um DSA Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.

Wie lange dauert die Lektion „Decode Ways und Pfade zählen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. House Robber: Rekurrenz aus Nehmen oder Überspringen
  2. Maximales Teilarray und Teilarray mit maximalem Produkt
  3. Word Break und String segmentieren
  4. Decode Ways und Pfade zählen
← Zurück zu DSA Interview Prep