剑指 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;
}
}
Python
class Solution(object):
def translateNum(self, num):
"""
:type num: int
:rtype: int
"""
if num <= 9:
return 1
arr = list(str(num))
n = len(arr)
a = b = c = 1
for i in range(1, n):
tmp = int(arr[i-1] + arr[i])
if 10 <= tmp <= 25:
c = a + b
else:
c = b
a, b = b, c
return c
C++
class Solution {
public:
int translateNum(int num) {
if (num <= 9) {
return 1;
}
string str = to_string(num);
int n = str.size();
int a = 1, b = 1, c = 1;
for (int i = 1; i < n; i++) {
int tmp = stoi(str.substr(i-1, 2));
if (tmp >= 10 && tmp <= 25) {
c = a + b;
} else {
c = b;
}
a = b;
b = c;
}
return c;
}
};
Go
func translateNum(num int) int {
if num <= 9 {
return 1
}
str := strconv.Itoa(num)
n := len(str)
a, b, c := 1, 1, 1
for i := 1; i < n; i++ {
tmp, _ := strconv.Atoi(str[i-1 : i+1])
if tmp >= 10 && tmp <= 25 {
c = a + b
} else {
c = b
}
a, b = b, c
}
return c
}
JS
/**
* @param {number} num
* @return {number}
*/
var translateNum = function(num) {
if (num <= 9) {
return 1;
}
let arr = String(num).split('');
let n = arr.length;
let a = 1;
let b = 1;
let c = 1;
for (let i = 2; i <= n; i++) {
// 计算第 i 和第 i-1 个字符的组合
let tmp = 10 * parseInt(arr[i - 2]) + parseInt(arr[i - 1]);
if (tmp >= 10 && tmp <= 25) {
c = a + b;
} else {
c = b;
}
// 迭代
a = b;
b = c;
}
return c;
};