题目:把数字翻译成字符串
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 :
输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
分析
这道题其实思路不难了。经典的动态规划题目。这道题的另一个出题的方向就是算能转换成最多的字符个数。道理是一样的。
动态规划最核心是什么?动态转换方程。对,一定要完全理解好这个方程,否则就会一直出错。这道题中每一个数,如果和他上一个数合起来成为两位数,如果这个两位数在10-25之间,那么这个位置所能表示的最多翻译方法是上一个位置的数目+上上一个位置的数目。我们来看看为什么。
例如有12258
- 首先得到1,那么只有一种可能。
- 得到2,那么有两种可能:一种是2保持本身得到一个字符,那么这种情况下的个数就是和前一个位置一样;第二种情况是和1合并成为12,所以一共有1+1=2种可能。
- 再次得到2 ,和上面的步骤二相同,1+2=3种
- 得到5,2+3=5
- 得到8,这里就不一样了,因为58不能表示为字符,所以只能8单独作为一个字符,所以和上个位置一样:5.
所以整个转态转换可以理解了吧。判断两位是否可以成为一个字符,然后再代入转态转换方程即可。
这个思想有两种实现方式:迭代和递归。两种方式都很好理解,思想是一样的,看下面代码就可以理解了。
代码实现
方法一:迭代
public static int translateNum(int num) {
if (num<10) return 1;
String s = String.valueOf(num);
int[] array = new int[s.length()+1];
array[0] = 1;
array[1] = 1;
for (int i=2;i<array.length;i++){
if (s.charAt(i-2)>'2'||s.charAt(i-2)<'1') array[i] = array[i-1];
else if (s.charAt(i-2)=='2'&&s.charAt(i-1)>'5') array[i] = array[i-1];
else array[i] = array[i-1]+array[i-2];
}
return array[array.length-1];
}
方法二:递归
public static int translateNum(int num) {
if (num>9&&num<26) return 2;
if (num<100) return 1;
if (num%100<26&&num%100>9){
return translateNum(num/10)+translateNum(num/100);
}
return translateNum(num/10);
}
复杂度分析
假设num的大小是n
- 时间复杂度:我们需要遍历数字num的长度
时间复杂度:O(logn)
- 空间复杂度:栈的深度和新建数组字符串的大小都是num的长度
空间复杂度:O(logn)