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

题目描述

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

示例 1:

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

提示：

0 <= num < 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$ 为给定的数字。

Python3

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)

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]$ 表示前 $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$ 的空间。