剑指offer46 把数字翻译成字符串【DP】

题目描述

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

示例 1:

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

提示:

  • 0 <= num < 231

解题思路

方法一:动态规划

先将数字转化为字符串进行,进而判断连续的两个字符组成的两位字符串是否在10~25的范围内,分为两种情况进行动态规划。

动态规划的转移方程为:

分为两种情况:

  • 第一种:第i位和第i-1位字符组成字符串 10~25范围内,则

$$
dp[i]=dp[i-1]+dp[i-2]
$$

  • 第二种:第i位和第i-1位字符组成字符串不在 10~25范围内,则

$$
dp[i]=dp[i-1]
$$

此题可对数组优化为两个变量进行。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int a = 1, b = 1;
for (int i = 1; i < s.length(); i++) {
String temp = s.substring(i - 1, i+1);
int c = a;
if (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) {
c = a + b;
}
b = a;
a = c;
}
return a;
}
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

资源

剑指offer46 把数字翻译成字符串【DP】

http://example.com/2021/05/28/剑指offer46-把数字翻译成字符串/

Author

John Doe

Posted on

2021-05-28

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.