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

Categories:

题目描述
思路分析
1. 解法一：动态规划滚动数组（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划滚动数组（推荐）

核心思路：

设 dp[i] 表示前 i 位数字的翻译种数。

若两位数在 10~25 之间，则 dp[i] = dp[i-1] + dp[i-2]，否则 dp[i] = dp[i-1]。

使用滚动变量代替数组节省空间。

复杂度分析：

时间复杂度：O(n)，其中 n 为数字长度。

空间复杂度：O(1)，仅使用常数变量。

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1;
        int b = 1;

        // 逐位判断能否两位翻译
        for (int i = 2; i <= s.length(); i++) {
            String sub = s.substring(i - 2, i);
            int c = (sub.compareTo("10") >= 0 && sub.compareTo("25") <= 0) ? a + b : b;
            a = b;
            b = c;
        }

        return b;
    }
}

func translateNum(num int) int {
    s := strconv.Itoa(num)
    a, b := 1, 1

    // 逐位判断能否两位翻译
    for i := 2; i <= len(s); i++ {
        sub := s[i-2 : i]
        c := b
        if sub >= "10" && sub <= "25" {
            c = a + b
        }
        a = b
        b = c
    }

    return b
}

相似题目

题目	难度	考察点
91. 解码方法	中等	动态规划
70. 爬楼梯	简单	DP
509. 斐波那契数	简单	DP
198. 打家劫舍	中等	DP
剑指 Offer 10- II. 青蛙跳台阶问题	简单	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/80659006