JZ46 把数字翻译成字符串

发表于 分类于 本文字数： 305 阅读时长 ≈ 1 分钟

JZ46 把数字翻译成字符串

描述

有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 $0<n≤90$

进阶：空间复杂度 $O(n)$，时间复杂度 $O(n)$

示例1

1
2
3
输入："12"
返回值：2
说明：2种可能的译码结果（”ab” 或”l”）

示例2

1
2
3
输入："31717126241541717"
返回值：192
说明：192种可能的译码结果

题解

和JZ19类似，只考虑当前字符单独处理还是和右侧一个一起处理。设$dp$为当前的解码方式数量。

  • 当只处理一个字符时，$dp = solv(nums.substr(1))$

  • 当后一个字符和当前字符组成数字小于大于等于10时，$dp += solve(nums.substr(2))$

边界条件：$nums$长度为0时返回1，$nums$首位为0时不合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <string>
using namespace std;

class Solution {
public:
    int solve(string nums) {
        if(nums.empty()) return 1;          // 空串，解码方式为 1
        if(nums[0] == '0') return 0;        // 前导 0 不合法

        int res = solve(nums.substr(1));    // 第一位单独解码

        if(nums.length() >= 2) {
            int twoDigit = stoi(nums.substr(0,2));
            if(twoDigit >= 10 && twoDigit <= 26) {
                res += solve(nums.substr(2));  // 前两位组合解码
            }
        }
        return res;
    }
};