面试题46. 把数字翻译成字符串
给定┅个数字我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”……,11 翻译成 “l”……,25 翻译成 “z”一个数字可能有多個翻译。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
-
dp[i] 表示从第0位到第i位可以有多少中字母
- 可以单独作为一位来翻译
- 如果第 i - 1 位和第 i 位组成的数字在 10 到 25 之间,可以把这两位连起来翻译
- 动态规划 + 字符串 + 滚动数组
官方题解和第一种方法两种不同- 用字符串存儲num的每一位
- 用了滚动数组替代dp减小空间复杂度
-
递归,根据末尾两位来分
- 我的公众号: 每日分享LeetCode, 让你走在路上坐在车上也能看算法题,欢迎大家扫码关注