LeetCode 91: Decode Ways (1D Dynamic Programming)

2026-03-18 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 91Dynamic ProgrammingString

Today we solve LeetCode 91 - Decode Ways.

Source: https://leetcode.com/problems/decode-ways/

LeetCode 91 DP transition diagram for one-digit and two-digit decodings

English

Problem Summary

Given a numeric string s, count how many ways it can be decoded where '1' -> 'A', ..., '26' -> 'Z'. A '0' cannot be decoded alone.

Key Insight

Let dp[i] be the number of ways to decode the prefix s[0..i-1]. At each position, we can transition from one-digit decoding and/or two-digit decoding if valid.

Brute Force and Limitations

Naive DFS tries all split choices and revisits the same suffix many times, causing exponential complexity. DP removes repeated subproblems.

Optimal Algorithm Steps (1D DP)

1) If first char is '0', return 0.
2) Initialize dp[0] = 1, dp[1] = 1.
3) For each i from 2 to n:
- If s[i-1] is not '0', add dp[i-1].
- If s[i-2..i-1] forms a number in [10, 26], add dp[i-2].
4) Return dp[n].

Complexity Analysis

Time: O(n).
Space: O(n) (can be optimized to O(1)).

Common Pitfalls

- Treating 0 as a valid single-digit decode.
- Accepting invalid two-digit numbers like 06.
- Missing boundary cases such as "10", "100", "230".

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            char c1 = s.charAt(i - 1);
            if (c1 != '0') dp[i] += dp[i - 1];

            int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];
    }
}

func numDecodings(s string) int {
    n := len(s)
    if n == 0 || s[0] == '0' {
        return 0
    }

    dp := make([]int, n+1)
    dp[0], dp[1] = 1, 1

    for i := 2; i <= n; i++ {
        if s[i-1] != '0' {
            dp[i] += dp[i-1]
        }
        two := int(s[i-2]-'0')*10 + int(s[i-1]-'0')
        if two >= 10 && two <= 26 {
            dp[i] += dp[i-2]
        }
    }

    return dp[n]
}

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0 || s[0] == '0') return 0;

        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];
    }
};

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0

        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]

            two = int(s[i - 2:i])
            if 10 <= two <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

var numDecodings = function(s) {
  const n = s.length;
  if (n === 0 || s[0] === '0') return 0;

  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    if (s[i - 1] !== '0') dp[i] += dp[i - 1];

    const two = Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }

  return dp[n];
};

中文

题目概述

给定一个只包含数字的字符串 s，请计算它有多少种解码方式，其中 '1' -> 'A'，...，'26' -> 'Z'。注意 '0' 不能单独解码。

核心思路

定义 dp[i] 为前缀 s[0..i-1] 的解码方案数。每一步都尝试两类转移：单字符转移（当前字符非 0）和双字符转移（当前两位在 10~26）。

基线解法与不足

暴力 DFS 会不断重复计算相同后缀，时间复杂度呈指数增长。用 DP 记录前缀结果后，每个位置只计算一次。

最优算法步骤（1D DP）

1）若首字符是 '0'，直接返回 0。
2）初始化 dp[0] = 1，dp[1] = 1。
3）从 i = 2 遍历到 n：
- 若 s[i-1] != '0'，则 dp[i] += dp[i-1]。
- 若两位数 s[i-2..i-1] 在 [10,26]，则 dp[i] += dp[i-2]。
4）返回 dp[n]。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（可进一步优化到 O(1)）。

常见陷阱

- 把 0 当成可单独解码字符。
- 把 06 这种前导零两位数误判为合法。
- 忽略 "10"、"100"、"230" 等边界输入。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            char c1 = s.charAt(i - 1);
            if (c1 != '0') dp[i] += dp[i - 1];

            int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];
    }
}

func numDecodings(s string) int {
    n := len(s)
    if n == 0 || s[0] == '0' {
        return 0
    }

    dp := make([]int, n+1)
    dp[0], dp[1] = 1, 1

    for i := 2; i <= n; i++ {
        if s[i-1] != '0' {
            dp[i] += dp[i-1]
        }
        two := int(s[i-2]-'0')*10 + int(s[i-1]-'0')
        if two >= 10 && two <= 26 {
            dp[i] += dp[i-2]
        }
    }

    return dp[n]
}

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (n == 0 || s[0] == '0') return 0;

        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];
    }
};

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0

        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1

        for i in range(2, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]

            two = int(s[i - 2:i])
            if 10 <= two <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

var numDecodings = function(s) {
  const n = s.length;
  if (n === 0 || s[0] === '0') return 0;

  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    if (s[i - 1] !== '0') dp[i] += dp[i - 1];

    const two = Number(s.slice(i - 2, i));
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }

  return dp[n];
};