长春网站排名优化公司,提供网站空间服务器,在阿里云做网站教程,营销型网站建设哪个好把数字翻译成字符串 题目描述示例示例1示例2 题解动态规划代码实现复杂度分析 总结 题目描述
有一种将字母编码成数字的方式#xff1a;‘a’-1, ‘b’-2, … , ‘z’-26。
现在给一串数字#xff0c;返回有多少种可能的译码结果。
数据范围#xff1a;字符串… 把数字翻译成字符串 题目描述示例示例1示例2 题解动态规划代码实现复杂度分析 总结 题目描述
有一种将字母编码成数字的方式‘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 个数字可以翻译成多少种不同的字符串。状态转移方程如下
如果当前数字 nums[i] 不为 0则 dp[i] dp[i-1]。如果当前数字 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);// 如果当前字符是 0if (nums[i] 0) {// 如果两位数无效如 00 或大于 26返回0if (two 0 || two 30) {return 0;}// 当前位置的解码方法数等于前两个字符的解码方法数dp[i1] dp[i-1];} // 如果两位数在 11 到 26 之间可以解码为一个字母else if (two 11 two 26) {// 当前位置的解码方法数等于前一个字符和前两个字符的解码方法数之和dp[i1] dp[i] dp[i-1];} // 其他情况当前字符单独解码else {dp[i1] 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”一百种情况。所以不需要考虑太多。
