一个简单的app多少钱_公司部门管理制度_百度写一篇文章多少钱_seo快速排名代理

力扣91题：解码方法详解（C语言实现）

题目描述

一条包含字母 A-Z 的消息通过以下映射进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，解码方法的总数是多少？

示例 1:

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入：s = "226"
输出：3
解释：它可以解码为 "BZ"（2 26）、"VF"（22 6）或者 "BBF"（2 2 6）。

---

解题思路

此题可以通过动态规划解决，定义 dp[i] 表示字符串前 i 个字符的解码方法总数。

状态转移方程

1. 单个字符解码：
   若当前字符 s[i-1] 可以单独解码（即 1 ≤ s[i-1] ≤ 9），则
   $$dp[i]+=dp[i-1]$$

2. 两个字符解码：
   若前一个字符和当前字符组成的数字可以解码（即 10 ≤ s[i-2:i] ≤ 26），则
   $$dp[i]+=dp[i-2]$$

边界条件

• 空字符串：只有一种解码方法，即 dp[0] = 1。
• 如果字符串以 0 开头，则无法解码，直接返回 0。

---

C语言实现

以下是基于上述思路的代码实现：

#include <stdio.h>
#include <string.h>int numDecodings(char *s) {int n = strlen(s);if (n == 0 || s[0] == '0') return 0;int dp[n + 1]; dp[0] = 1; // 空字符串的解码方法数dp[1] = 1; // 单个字符的解码方法数（非0）for (int i = 2; i <= n; i++) {dp[i] = 0;// 单个字符解码if (s[i - 1] != '0') {dp[i] += dp[i - 1];}// 两个字符解码int twoDigit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');if (twoDigit >= 10 && twoDigit <= 26) {dp[i] += dp[i - 2];}}return dp[n];
}int main() {char s[] = "226";printf("解码方法总数: %d\n", numDecodings(s));return 0;
}

---

测试用例

示例1

输入：s = "12"
输出：2

示例2

输入：s = "226"
输出：3

示例3

输入：s = "06"
输出：0

---

复杂度分析

1. 时间复杂度：
   遍历字符串一次，故时间复杂度为 $O(n)$。

2. 空间复杂度：
   使用了额外的数组 dp，故空间复杂度为 $O(n)$。