LeetCode 91. 解码方法

Categories:

Tags:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 91. 解码方法

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i] 表示前 i 个字符的解码方法数。

若 s[i-1] 不为 0，则 dp[i] += dp[i-1]。

若 s[i-2..i-1] 在 10~26 之间，则 dp[i] += dp[i-2]。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串长度。

空间复杂度：O(1)，只需常数变量滚动。

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

        int prev2 = 1;
        int prev1 = 1;

        for (int i = 2; i <= s.length(); i++) {
            int cur = 0;
            char c1 = s.charAt(i - 1);
            char c0 = s.charAt(i - 2);

            if (c1 != '0') {
                cur += prev1;
            }

            int val = (c0 - '0') * 10 + (c1 - '0');
            if (val >= 10 && val <= 26) {
                cur += prev2;
            }

            prev2 = prev1;
            prev1 = cur;
        }

        return prev1;
    }
}

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

	prev2 := 1
	prev1 := 1

	for i := 2; i <= len(s); i++ {
		cur := 0
		c1 := s[i-1]
		c0 := s[i-2]

		if c1 != '0' {
			cur += prev1
		}

		val := int(c0-'0')*10 + int(c1-'0')
		if val >= 10 && val <= 26 {
			cur += prev2
		}

		prev2 = prev1
		prev1 = cur
	}

	return prev1
}

相似题目

题目	难度	考察点
70. 爬楼梯	简单	动态规划
91. 解码方法	中等	动态规划
639. 解码方法 II	困难	动态规划
322. 零钱兑换	中等	动态规划
198. 打家劫舍	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/38032399