46. 把数字翻译成字符串【难】

河曲智叟 · 2024-9-4 17:42:55

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

x

comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9846.%20%E6%8A%8A%E6%95%B0%E5%AD%97%E7%BF%BB%E8%AF%91%E6%88%90%E5%AD%97%E7%AC%A6%E4%B8%B2/README.md

面试题 46. 把数字翻译成字符串

标题描述

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

示例 1:

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

复制代码

提示：

0 <= num < 231

  解法

  方法一：记忆化搜刮

我们先将数字 num 转为字符串                                  s                            s                s，字符串                                  s                            s                s 的长度记为                                  n                            n                n。
然后我们设计一个函数                                        d                         f                         s                         (                         i                         )                               dfs(i)                   dfs(i)，表现从第                                        i                               i                   i 位数字开始的不同翻译的数目。那么答案就是                                  d                      f                      s                      (                      0                      )                            dfs(0)                dfs(0)。
函数                                  d                      f                      s                      (                      i                      )                            dfs(i)                dfs(i) 的盘算如下：

如果 i ≥ n − 1 i \ge n - 1 i≥n−1，分析已经翻译到最后一个数字，只有一种翻译方法，返回 1 1 1；
否则，我们可以选择翻译第 i i i 位数字，此时翻译方法数目为 d f s ( i + 1 ) dfs(i + 1) dfs(i+1)；如果第 i i i 位数字和第 i + 1 i + 1 i+1 位数字可以构成一个有效的字符（即 s [ i ] = = 1 s == 1 s==1 或者 ( s [ i ] = = 2 s == 2 s==2 且 s [ i + 1 ] < 6 s[i + 1] \lt 6 s[i+1]<6)），那么我们还可以选择翻译第 i i i 和第 i + 1 i + 1 i+1 位数字，此时翻译方法数目为 d f s ( i + 2 ) dfs(i + 2) dfs(i+2)。因此 d f s ( i ) = d f s ( i + 1 ) + d f s ( i + 2 ) dfs(i) = dfs(i+1) + dfs(i+2) dfs(i)=dfs(i+1)+dfs(i+2)。

过程中我们可以使用记忆化搜刮，将已经盘算过的 d f s ( i ) dfs(i) dfs(i) 的值存储起来，避免重复盘算。
时间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum)，空间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum)。此中 n u m num num 为给定的数字。
 Python3

class Solution:
def translateNum(self, num: int) -> int:
 @cache
 def dfs(i):
 if i >= n - 1: #第i-1位数字往后只有一种翻译方式
 return 1

 ans = dfs(i + 1)
 if s[i] == "1" or (s[i] == "2" and s[i + 1] < "6"):#核心：当有两位数字且不大于26时，就会出现两种翻译方式，从而翻译种数dfs(i)=dfs(i+1)+dfs(i+1)
 ans += dfs(i + 2)
 return ans
 s = str(num)
 n = len(s)
 return dfs(0)
复制代码
Java

class Solution {
private int n;
private char[] s;
private Integer[] f;
public int translateNum(int num) {
 s = String.valueOf(num).toCharArray();
 n = s.length;
 f = new Integer[n];
 return dfs(0);
}
private int dfs(int i) {
 if (i >= n - 1) {
 return 1;
 }
 if (f[i] != null) {
 return f[i];
 }
 int ans = dfs(i + 1);
 if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '6')) {
 ans += dfs(i + 2);
 }
 return f[i] = ans;
}
}
复制代码
C++

class Solution {
public:
int translateNum(int num) {
 string s = to_string(num);
 int n = s.size();
 int f[12]{};
 function<int(int)> dfs = [&](int i) -> int {
 if (i >= n - 1) {
 return 1;
 }
 if (f[i]) {
 return f[i];
 }
 int ans = dfs(i + 1);
 if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '6')) {
 ans += dfs(i + 2);
 }
 return f[i] = ans;
 };
 return dfs(0);
}
};
复制代码
Go

func translateNum(num int) int {
s := strconv.Itoa(num)
n := len(s)
f := [12]int{}
var dfs func(int) int
dfs = func(i int) int {
if i >= n-1 {
return 1
}
if f[i] != 0 {
return f[i]
}
ans := dfs(i + 1)
if s[i] == '1' || (s[i] == '2' && s[i+1] < '6') {
ans += dfs(i + 2)
}
f[i] = ans
return ans
}
return dfs(0)
}
复制代码
TypeScript

function translateNum(num: number): number {
const s = num.toString();
const n = s.length;
const f = new Array(n).fill(0);
const dfs = (i: number): number => {
 if (i >= n - 1) {
 return 1;
 }
 if (f[i]) {
 return f[i];
 }
 let ans = dfs(i + 1);
 if (s[i] === '1' || (s[i] === '2' && s[i + 1] < '6')) {
 ans += dfs(i + 2);
 }
 f[i] = ans;
 return ans;
};
return dfs(0);
}
复制代码
Rust

impl Solution {
pub fn translate_num(num: i32) -> i32 {
 let mut a = 1;
 let mut b = 1;
 let str = num.to_string();
 for i in 0..str.len() - 1 {
 let c = a + b;
 a = b;
 let num = str[i..i + 2].parse::<i32>().unwrap();
 if num >= 10 && num < 26 {
 b = c;
 }
 }
 b
}
}
复制代码
JavaScript

/**
* @param {number} num
* @return {number}
*/
var translateNum = function (num) {
const s = num.toString();
const n = s.length;
const f = new Array(n).fill(0);
const dfs = i => {
 if (i >= n - 1) {
 return 1;
 }
 if (f[i]) {
 return f[i];
 }
 let ans = dfs(i + 1);
 if (s[i] === '1' || (s[i] === '2' && s[i + 1] < '6')) {
 ans += dfs(i + 2);
 }
 f[i] = ans;
 return ans;
};
return dfs(0);
};
复制代码
C#

public class Solution {
public int TranslateNum(int num) {
 var s = num.ToString();
 int n = s.Length;
 int a = 1, b = 1;
 for (int i = 1; i < n; ++i) {
 int c = b;
 if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '6')) {
 c += a;
 }
 a = b;
 b = c;
 }
 return b;
}
}
复制代码
Swift

class Solution {
private var n: Int = 0
private var s: [Character] = []
private var memo: [Int?] = []
func translateNum(_ num: Int) -> Int {
 s = Array(String(num))
 n = s.count
 memo = [Int?](repeating: nil, count: n)
 return dfs(0)
}
private func dfs(_ i: Int) -> Int {
 if i >= n - 1 {
 return 1
 }
 if let cachedResult = memo[i] {
 return cachedResult
 }
 var ans = dfs(i + 1)
 if s[i] == "1" || (s[i] == "2" && s[i + 1] < "6") {
 ans += dfs(i + 2)
 }
 memo[i] = ans
 return ans
}
}
复制代码
方法二：动态规划

我们可以将方法一中的记忆化搜刮改为动态规划。
定义 f [ i ] f f 表现前 i i i 个数字的不同翻译的数目，那么答案就是 f [ n ] f[n] f[n]。初始化 f [ 0 ] = 1 f[0] = 1 f[0]=1, f [ 1 ] = 1 f[1] = 1 f[1]=1。
我们可以从前今后盘算 f [ i ] f f 的值，对于每个 i i i，我们可以选择翻译第 i i i 个数字，此时翻译方法数目为 f [ i − 1 ] f[i - 1] f[i−1]；如果第 i − 1 i-1 i−1 个数字和第 i i i 个数字可以构成一个有效的字符（即 s [ i − 1 ] = = 1 s[i - 1] == 1 s[i−1]==1 或者 s [ i − 1 ] = = 2 s[i - 1] == 2 s[i−1]==2 且 s [ i ] < 6 s \lt 6 s<6），那么我们还可以选择翻译第 i − 1 i - 1 i−1 和第 i i i 个数字，此时翻译方法数目为 f [ i − 2 ] f[i - 2] f[i−2]。因此 f [ i ] = f [ i − 1 ] + f [ i − 2 ] f = f[i-1] + f[i-2] f=f[i−1]+f[i−2]。
由于 f [ i ] f f 只与 f [ i − 1 ] f[i - 1] f[i−1] 和 f [ i − 2 ] f[i - 2] f[i−2] 有关，因此我们可以只用两个变量来存储 f [ i − 1 ] f[i - 1] f[i−1] 和 f [ i − 2 ] f[i - 2] f[i−2] 的值，从而省去数组 f f f 的空间。
时间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum)，空间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum)。此中 n u m num num 为给定的数字。
 Python3

class Solution:
def translateNum(self, num: int) -> int:
 s = str(num)
 n = len(s)
 a = b = 1
 for i in range(2, n+1):
 c = b
 if s[i - 2] == '1' or (s[i - 2] == '2' and s[i-1] < '6'):#注意：第i个数字对应第i-1位
 c += a
 a, b = b, c
 return b
复制代码
Java

class Solution {
public int translateNum(int num) {
 char[] s = String.valueOf(num).toCharArray();
 int n = s.length;
 int a = 1, b = 1;
 for (int i = 1; i < n; ++i) {
 int c = b;
 if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '6')) {
 c += a;
 }
 a = b;
 b = c;
 }
 return b;
}
}
复制代码
C++

class Solution {
public:
int translateNum(int num) {
 string s = to_string(num);
 int n = s.size();
 int a = 1, b = 1;
 for (int i = 1; i < n; ++i) {
 int c = b;
 if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '6')) {
 c += a;
 }
 a = b;
 b = c;
 }
 return b;
}
};
复制代码
Go

func translateNum(num int) int {
s := strconv.Itoa(num)
n := len(s)
a, b := 1, 1
for i := 1; i < n; i++ {
c := b
if s[i-1] == '1' || (s[i-1] == '2' && s[i] < '6') {
c += a
}
a, b = b, c
}
return b
}
复制代码
TypeScript

function translateNum(num: number): number {
const s = num.toString();
const n = s.length;
let a = 1;
let b = 1;
for (let i = 1; i < n; ++i) {
 let c = b;
 if (s[i - 1] === '1' || (s[i - 1] === '2' && s[i] < '6')) {
 c += a;
 }
 a = b;
 b = c;
}
return b;
}
复制代码
Rust

impl Solution {
fn dfs(s: &String, i: usize, res: &mut i32) {
 if i >= s.len() {
 return;
 }
 let val = s[i - 1..=i].parse::<i32>().unwrap();
 if val >= 10 && val <= 25 {
 *res += 1;
 Self::dfs(s, i + 2, res);
 }
 Self::dfs(s, i + 1, res);
}
pub fn translate_num(num: i32) -> i32 {
 let s = num.to_string();
 let mut res = 1;
 Self::dfs(&s, 1, &mut res);
 res
}
}
复制代码
JavaScript

/**
* @param {number} num
* @return {number}
*/
var translateNum = function (num) {
const s = num.toString();
const n = s.length;
let a = 1;
let b = 1;
for (let i = 1; i < n; ++i) {
 let c = b;
 if (s[i - 1] === '1' || (s[i - 1] === '2' && s[i] < '6')) {
 c += a;
 }
 a = b;
 b = c;
}
return b;
};
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

用户名		自动登录	找回密码
密码			立即注册

46. 把数字翻译成字符串【难】

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

0 个回复

快速回复

楼主热帖

标签云