【LeetCode-每日一题】-面试题46. 把数字翻译成字符串

怼烎@ 2023-02-17 06:19 89阅读 0赞

# 1. 题目描述 #

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。  
示例 1:  
输入: 12258  
输出: 5  
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

# 2. 题目分析 #

1.  这个题目类型和跳台阶差不多，一阶或者两阶的跳，求到N阶有多少种方法
2.  对于12258来说，可拆分为以下几部分：**1 2 2 5 8 、 12 2 5 8 、 12 25 8 、1 22 5 8 、1 2 25 8**
3.  相当于从1开始往后跳，一个数或者两个数（注意取值范围 0~25）
4.  当前如果是N阶的话，可以F(n - 1) + 1或者F(n - 2)+2  
    F(n) = F(n-1) + F(n-2);  
    这里需要注意一下，当前获取的数字只有在10~25之间才是有效的，否则是无效的

# 3. 题目代码 #

class Solution {
        
       public static int translateNum(int num) {
        
    		// 将num转为String类型
    		String string = String.valueOf(num);
    		// 如果当前的数字小于10的话，证明只有一种结果，直接返回1
    		if (num < 10) {
        
    			return 1;
    		}
    		int[] dp = new int[string.length() + 1];
    		dp[0] = 1;
    		dp[1] = 1;
    		for (int i = 2; i < string.length(); i++) {
        
    			String x = string.substring(i - 2, i);
    			if (x.compareTo("10") >= 0 && x.compareTo("25") <= 0) {
        
    				dp[i] = dp[i - 1] + dp[i - 2];
    			} else {
        
    				dp[i] = dp[i - 1];
    			}
    		}
    		return dp[string.length() - 1];
    	}