解题思路

这是一道字符串解码题，关键点是：

  1. 字母到数字的映射规则：'a'->1, 'b'->2, ..., 'z'->26
  2. 一个数字可能有多种解码方式，比如"12"可以解码为"ab"或"l"
  3. 需要考虑数字的组合是否有效（必须在1-26范围内）

解题步骤：

  1. 使用动态规划， 表示前 个数字的解码方式数量
  2. 对于每个位置 ，考虑两种情况：
    • 单独解码当前数字
    • 将当前数字与前一个数字组合解码
  3. 注意处理前导零和无效组合的情况

关键点解释

  1. 表示前 个数字的解码方式数量
  2. 状态转移考虑两种情况：
    • 单独解码：当前数字不为0时，可以继承 的方案数
    • 组合解码：当前数字与前一个数字组合在10-26范围内时，可以继承 的方案数
  3. 注意处理边界情况：
    • 前导零无法解码
    • 单个零无法单独解码
    • 两位数必须在10-26范围内

代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    
    // dp[i]表示前i个数字的解码方式数量
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;  // 空字符串有1种解码方式
    
    for(int i = 1; i <= n; i++) {
        // 当前数字单独解码
        if(s[i-1] != '0') {
            dp[i] += dp[i-1];
        }
        
        // 与前一个数字组合解码
        if(i > 1) {
            int num = (s[i-2] - '0') * 10 + (s[i-1] - '0');
            if(num >= 10 && num <= 26) {
                dp[i] += dp[i-2];
            }
        }
    }
    
    cout << dp[n] << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        
        // dp[i]表示前i个数字的解码方式数量
        long[] dp = new long[n + 1];
        dp[0] = 1;  // 空字符串有1种解码方式
        
        for(int i = 1; i <= n; i++) {
            // 当前数字单独解码
            if(s.charAt(i-1) != '0') {
                dp[i] += dp[i-1];
            }
            
            // 与前一个数字组合解码
            if(i > 1) {
                int num = (s.charAt(i-2) - '0') * 10 + (s.charAt(i-1) - '0');
                if(num >= 10 && num <= 26) {
                    dp[i] += dp[i-2];
                }
            }
        }
        
        System.out.println(dp[n]);
    }
}

s = input()
n = len(s)

# dp[i]表示前i个数字的解码方式数量
dp = [0] * (n + 1)
dp[0] = 1  # 空字符串有1种解码方式

for i in range(1, n + 1):
    # 当前数字单独解码
    if s[i-1] != '0':
        dp[i] += dp[i-1]
    
    # 与前一个数字组合解码
    if i > 1:
        num = int(s[i-2:i])
        if 10 <= num <= 26:
            dp[i] += dp[i-2]

print(dp[n])

算法及复杂度

  • 算法：动态规划。使用dp数组记录每个位置的解码方式数量。
  • 时间复杂度：，其中 是输入数字串的长度。
  • 空间复杂度：，需要dp数组存储中间结果。