剑指offer-46

剑指 Offer 46. 把数字翻译成字符串

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

示例：

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

官方题解

首先我们来通过一个例子理解一下这里「翻译」的过程：我们来尝试翻译 1402。

分成两种情况：

• 首先我们可以把每一位单独翻译，既 [1,4,0,2]，翻译的结果是 beac
• 然后我们考虑组合某些连续的两位：
  • [14,0,2]，翻译的结果是 oac。
  • [1,40,2]，这种情况是不合法的，因为40不能翻译为任何字母
  • [1,4, 02] 这种情况也是不合法的，含有前导0的两位数不在题目规定的翻译规则中，那么 [14,02]也是不合法的

那么我们可以归纳出翻译的规则，字符串的第 $i$ 位置：

• 可以单独作为一位来翻译
• 如果第 $i-1$ 位和第 $i$ 位组成的数组在 10 到25之间，可以把这两位连起来翻译

我们可以考虑用 $f(i)$ 表示以第 $i$ 位结尾的前缀串翻译的方案数，考虑第 $i$ 位单独翻译和与前一位连接起来再翻译对 $f(i)$ 的贡献。单独翻译对 $f(i)$ 的贡献为 $f(i-1)$；如果第 $i-1$ 位存在，并且第 $i-1$ 位和第 $i$ 位形成的数字$x$ 满足 $10\leq x \leq 25$，那么就可以把第 $i-1$ 位和第 $i$ 位连起来一起翻译，对 $f(i)$ 的贡献为 $f(i-2)$，否则为0。我们可以列出这样的动态规划转移方程：
$$
f(i) = f(i-1)+f(i-2)[i-1 >= 0, 10\leq x \leq 25]
$$
边界条件是 $f(-1)=0, f(0)=1$。方程 中$[c]$的意思是 c 为真的时候 $[c] =1$，否则 $[c] = 0$。

class Solution:
    def translateNum(self, num: int) -> int:
        str1 = str(num)

        p = 0
        q = 0
        r = 1

        for i in range(len(str1)):
            p = q
            q = r 
            r = 0

            r += q
            if i == 0: continue

            pre = str1[i-1:i-1+2]

            if pre <= "25" and pre >= "10":
                r+=p
        
        # print(r)
        return r

class Solution {
    public int translateNum(int num) {
        String s = Integer.toString(num);
		if(s.length() == 1) return 1;
		
		int[] dp = new int[s.length() + 1];
		dp[0] = dp[1] = 1;
		int res = 1;
		for (int i = 1; i < s.length(); i++) {
			String temp = s.substring(i - 1,i + 1); 
			if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) 
				dp[i + 1] = dp[i - 1] + dp[i];
			else 
				dp[i + 1] = dp[i];
		}
		
		return dp[s.length()];
    }
}