跳转至

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

题目描述

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

 

示例 1:

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

 

提示：

  • 0 <= num < 231

解法

方法一：记忆化搜索

思考

每位可单独翻译，两位若在 \(10\sim 25\) 也可合译，方案数满足类似斐波那契的递推，子问题重叠。

令 \(dfs(i)\) 为从位置 \(i\) 起的方案数：必加 \(dfs(i+1)\)，合法双位再加 \(dfs(i+2)\)。记忆化避免重复。

我们先将数字 num 转为字符串 \(s\)，字符串 \(s\) 的长度记为 \(n\)。

然后我们设计一个函数 \(dfs(i)\)，表示从索引为 \(i\) 的数字开始的不同翻译的数目。那么答案就是 \(dfs(0)\)。

函数 \(dfs(i)\) 的计算如下：

  • 如果 \(i \ge n - 1\)，说明已经翻译到最后一个数字或者越过最后一个字符，均只有一种翻译方法，返回 \(1\)；
  • 否则，我们可以选择翻译索引为 \(i\) 的数字，此时翻译方法数目为 \(dfs(i + 1)\)；如果索引为 \(i\) 的数字和索引为 \(i + 1\) 的数字可以组成一个有效的字符（即 \(s[i] == 1\) 或者 \(s[i] == 2\) 且 \(s[i + 1] \lt 6\)），那么我们还可以选择翻译索引为 \(i\) 和索引为 \(i + 1\) 的数字，此时翻译方法数目为 \(dfs(i + 2)\)。因此 \(dfs(i) = dfs(i+1) + dfs(i+2)\)。

过程中我们可以使用记忆化搜索，将已经计算过的 \(dfs(i)\) 的值存储起来，避免重复计算。

时间复杂度 \(O(\log num)\)，空间复杂度 \(O(\log num)\)。其中 \(num\) 为给定的数字。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def translateNum(self, num: int) -> int:
        @cache
        def dfs(i):
            if i >= n - 1:
                return 1
            ans = dfs(i + 1)
            if s[i] == "1" or (s[i] == "2" and s[i + 1] < "6"):
                ans += dfs(i + 2)
            return ans

        s = str(num)
        n = len(s)
        return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @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);
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
    }
}

方法二：动态规划

思考

记忆化已给出相同转移，递归栈与哈希缓存仍占额外空间。从左到右滚动两个变量即可，转移与 \(dfs(i+1)\)、\(dfs(i+2)\) 对应。

我们可以将方法一中的记忆化搜索改为动态规划。

定义 \(f[i]\) 表示前 \(i\) 个数字的不同翻译的数目，那么答案就是 \(f[n]\)。初始化 \(f[0] = 1\), \(f[1] = 1\)。

我们可以从前往后计算 \(f[i]\) 的值，对于每个 \(i\)，我们可以选择翻译第 \(i\) 个数字，此时翻译方法数目为 \(f[i - 1]\)；如果第 \(i-1\) 个数字和第 \(i\) 个数字可以组成一个有效的字符（即 \(s[i - 1] == 1\) 或者 \(s[i - 1] == 2\) 且 \(s[i] \lt 6\)），那么我们还可以选择翻译第 \(i - 1\) 和第 \(i\) 个数字，此时翻译方法数目为 \(f[i - 2]\)。因此 \(f[i] = f[i-1] + f[i-2]\)。

由于 \(f[i]\) 只与 \(f[i - 1]\) 和 \(f[i - 2]\) 有关，因此我们可以只用两个变量来存储 \(f[i - 1]\) 和 \(f[i - 2]\) 的值，从而省去数组 \(f\) 的空间。

时间复杂度 \(O(\log num)\)，空间复杂度 \(O(\log num)\)。其中 \(num\) 为给定的数字。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        n = len(s)
        a = b = 1
        for i in range(1, n):
            c = b
            if s[i - 1] == '1' or (s[i - 1] == '2' and s[i] < '6'):
                c += a
            a, b = b, c
        return b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @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;
};

评论