每日一题——把数字翻译成字符串

题目描述

有一种将字母编码成数字的方式：‘a’->1, ‘b’->2, … , ‘z’->26。

现在给一串数字，返回有多少种可能的译码结果。

数据范围：字符串长度满足 (0 < n \leq 90)

进阶：空间复杂度 (O(n))，时间复杂度 (O(n))

示例

示例1

输入：

"12"

返回值：

2

说明：
2种可能的译码结果（“ab” 或 “l”）

示例2

输入：

"31717126241541717"

返回值：

192

说明：
192种可能的译码结果

题解

动态规划

我们可以使用动态规划来解决这个问题。设 dp[i] 表示前 i 个数字可以翻译成多少种不同的字符串。状态转移方程如下：

1. 如果当前数字 nums[i] 不为 0，则 dp[i] += dp[i-1]。
2. 如果当前数字 nums[i-1] 和 nums[i] 组成的两位数在 10 到 26 之间，则 dp[i] += dp[i-2]。

边界条件：

• dp[0] = 1，表示空字符串有一种翻译方式。
• dp[1] = 1，如果第一个字符不为 0，则有一种翻译方式。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 解码函数
int solve(char* nums) {
    int length = strlen(nums); // 获取输入字符串的长度
    if (length == 0) return 0; // 如果字符串为空，返回0

    // 分配动态规划数组，dp[i] 表示前 i 个字符的解码方法数
    int* dp = (int*)calloc(length + 1, sizeof(int));
    dp[0] = 1; // 空字符串有一种解码方式

    // 初始化第一个字符的解码方法数
    if (nums[0] > '0' && nums[0] <= '9') {
        dp[1] = 1; // 如果第一个字符是有效的数字（1-9），有一种解码方式
    } else {
        return 0; // 如果第一个字符无效（如 '0'），直接返回0
    }

    // 遍历字符串，计算每个位置的解码方法数
    for (int i = 1; i < length; i++) {
        // 将当前字符和前一个字符组合成一个两位数
        int two = (nums[i-1] - '0') * 10 + (nums[i] - '0');

        // 如果当前字符是 '0'
        if (nums[i] == '0') {
            // 如果两位数无效（如 '00' 或大于 '26'），返回0
            if (two == 0 || two >= 30) {
                return 0;
            }
            // 当前位置的解码方法数等于前两个字符的解码方法数
            dp[i+1] = dp[i-1];
        } 
        // 如果两位数在 11 到 26 之间，可以解码为一个字母
        else if (two >= 11 && two <= 26) {
            // 当前位置的解码方法数等于前一个字符和前两个字符的解码方法数之和
            dp[i+1] = dp[i] + dp[i-1];
        } 
        // 其他情况，当前字符单独解码
        else {
            dp[i+1] = dp[i];
        }
    }

    // 获取最终结果
    int result = dp[length];
    free(dp); // 释放动态规划数组
    return result;
}

int main() {
    char nums[] = "226"; // 示例输入
    int result = solve(nums); // 调用解码函数
    printf("Number of ways to decode: %d\n", result); // 打印结果
    return 0;
}

复杂度分析

• 时间复杂度：(O(n))，其中 (n) 是字符串的长度。我们只需要遍历一次字符串即可。
• 空间复杂度：(O(n))，用于存储动态规划数组 dp。

总结

本题通过动态规划的方法，将问题分解为子问题，逐步求解。通过状态转移方程，我们可以有效地计算出所有可能的译码结果。这题最傻逼的就是如何处理0，还好只要考虑“00”到“99”一百种情况。所以不需要考虑太多。