💬 Discord
Sign In
NeetCode #668LC-91Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#668 · #91 · Decode Ways(解码方法)

📌 Problem Statement & Constraints

A message of digits can be decoded where A through Z map to the digit strings 1 through 26. Given a digit string s, return the number of ways to decode it. Constraints: 1 <= s.length <= 100, and s contains only digits, possibly with leading zeros.

💡 Core Algorithmic Approaches

  1. Let dp[i] be the number of ways to decode the first i characters.
  2. A single digit s[i-1] contributes dp[i-1] ways when it is not the digit zero.
  3. A two-digit group s[i-2..i-1] contributes dp[i-2] ways when its value lies between 10 and 26 inclusive.
  4. The recurrence sums the valid contributions; a zero digit can only be consumed as the second digit of a valid group.

💻 Benchmark Python3 Implementation

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        prev2 = 1                      # dp[0]: the empty prefix
        prev1 = 0 if s[0] == "0" else 1  # dp[1]
        for i in range(2, n + 1):
            cur = 0
            if s[i - 1] != "0":        # single-digit decode
                cur += prev1
            two = int(s[i - 2:i])      # two-digit decode
            if 10 <= two <= 26:
                cur += prev2
            prev2, prev1 = prev1, cur
        return prev1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass with constant work per index.
💾 Space Complexity
O(1): two rolling values.

⚠️ Interview Pitfalls & Follow-ups

  • Treating the digit zero as a decodable single digit: there is no letter for zero; it must attach to a preceding one or two.
  • Allowing two-digit values above 26: groups such as 27 and 30 are invalid and must be excluded.
  • Forgetting the leading-zero case: the input 06 has 0 decodings, which the prev1 = 0 initialisation handles.
  • Initialising dp[0] to 0: it must be 1 so that a valid two-digit opening group contributes one way.