剑指 Offer 46. 把数字翻译成字符串

本问题对应的 leetcode 原文链接:剑指 Offer 46. 把数字翻译成字符串

问题描述

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示:

  • 0 <= num < 2^31

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int translateNum(int num) {
        if(num <= 9){
            return 1;
        }
        char[] arr = String.valueOf(num).toCharArray();
        int n = arr.length;
        //int[] dp = new int[n + 1];
        // f(n) = f(n-1) + f(n-2)
        int a = 1;
        int b = 1;
        int c = 1;
        // 优化 a,b,c
        for(int i = 2; i <= n; i++){
            // 计算第i和第i-1个字符的组合
            int tmp = 10 * (arr[i-2] - '0') + (arr[i-1] - '0');
            if(tmp >= 10 && tmp <= 25){
                c = a + b;
            }else{
                c = b;
            }
            //迭代
            a = b;
            b = c;
        }

        return c;
    }
}

发表回复

后才能评论