Ex46 把数字翻译成字符串

题目描述

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

解题思路

将数字转换为字符串，使用很简单的递归，只需要注意这几种情况就可以了：

• num最多有两位；
• 当num为1位时，肯定可以翻译成某个字母的；
• 当num位2位时，数字应该小于26，且第一位不为0。

代码

class Solution {
 public:
  int translateNum(int num) {
    std::string str = std::to_string(num);
    int count = 0;
    count += translate_num(str, 1);
    if (str.size() >= 2 && std::stoi(str.substr(0, 2)) < 26 && str[0] != '0') {
      count += translate_num(str, 2);
    }
    return count;
  }

 private:
  int translate_num(std::string &str, int start) {
    if (start >= str.size() - 1) {
      return 1;
    }
    int count = 0;
    count += translate_num(str, start + 1);
    if (str.size() - start >= 2 && std::stoi(str.substr(start, 2)) < 26 &&
        str[start] != '0') {
      count += translate_num(str, start + 2);
    }
    return count;
  }
};

结果

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.2 MB, 在所有 C++ 提交中击败了29.92%的用户