题目链接

LeetCode

题目描述

给定一个数字，按照如下规则翻译成字符串：1 翻译成 “a”，2 翻译成 “b”… 26 翻译成 “z”。一个数字有多种翻译可能，例如 12258 一共有 5 种，分别是 abbeh，lbeh，aveh，abyh，lyh。实现一个函数，用来计算一个数字有多少种不同的翻译方法。

解题思路

动态规划

46. 把数字翻译成字符串 - 图1

  1. class Solution {
  2. public:
  3.     int numDecodings(string s) {
  4.         if (s[0] == '0') return 0;
  5.         vector<int> dp(s.size()+1);
  6.         // dp[0]表示s[-1]的状态， dp[1] 表示 s[0]的状态
  7.         // dp[i] 表示 s[i-1]的状态
  8.         dp[0]=1;dp[1]=1;
  9.         for (int i =1; i < s.size(); i++) {
  10.             if (s[i] == '0')//1.s[i]为0的情况  
  11.                 if (s[i - 1] == '1' || s[i - 1] == '2') //s[i - 1]等于1或2的情况 唯一译码，不增加情况
  12.                     dp[i+1] = dp[i-1]; //由于s[1]指第二个下标，对应为dp[2],所以dp的下标要比s大1，故为dp[i+1]
  13.                 else  //这里要好好理解一下，比如给定340, 输出可行的编码数为0， 因为0和40都无法转换
  14.                     return 0;
  15.             else //2.s[i]不为0的情况
  16.                 if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))//s[i-1]s[i]两位数要小于26的情况
  17.                     dp[i+1] = dp[i]+dp[i-1];
  18.                 else//其他情况 当上述条件都不满足，维持上一个状态
  19.                     dp[i+1] = dp[i];
  20.         }
  21.         return dp[s.size()]; //返回dp[n] 即最后 s[n-1] 的状态
  22.     }
  23. };
  • 时间复杂度：O(n)。

  • 空间复杂度：O(n)。

    1. // 因为dp[i]只和前两项有关，所以用单变量代替数组
    2. class Solution {
    3. public:
    4.   int numDecodings(string s) {
    5.       if (s[0] == '0') return 0;
    6.       int pre=1,cur=1;
    7.       for (int i =1; i < s.size(); i++) {
    8.           int tmp = cur;
    9.           if (s[i] == '0')//1.s[i]为0的情况  
    10.               if (s[i - 1] == '1' || s[i - 1] == '2') //s[i - 1]等于1或2的情况 唯一译码，不增加情况
    11.                   cur = pre; //由于s[1]指第二个下标，对应为dp[2],所以dp的下标要比s大1，故为dp[i+1]
    12.               else  //这里要好好理解一下，比如给定340, 输出可行的编码数为0， 因为0和40都无法转换
    13.                   return 0;
    14.           else //2.s[i]不为0的情况
    15.               if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))//s[i-1]s[i]两位数要小于26的情况
    16.                   cur = cur+pre;
    17.               else//其他情况 当上述条件都不满足，维持上一个状态
    18.                   cur = tmp;
    19.           pre = tmp;
    20.       }
    21.       return cur; //返回dp[n] 即最后 s[n-1] 的状态
    22.   }
    23. };

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)。

leetcode解法

  1. class Solution {
  2. public:
  3.     int translateNum(int num) {
  4.         string s = to_string(num);
  5.         int pre = 1, cur = 1;
  6.         for (int i =1; i < s.size(); i++) {
  7.             int tmp = cur; 
  8.             if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '5'))
  9.                 cur = cur + pre;
  10.             pre = tmp;
  11.         }
  12.         return cur;
  13.     }
  14. };
  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。