题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码:

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串,请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)。

题意

输入的数字是字符串,也就是说输入可能会包含0~9,但是编码方式并没有给出0的单独编码,所以当输入的字符串包含0的时候,需要作特殊的考虑。

当输入字符串没有0时

从简单入手,也就是没有0混在输入字符串中的时候,带0的稍后考虑。

动态规划的问题往往需要一步步推演,才能较快的找到前后关系,下面以"1221"输入为例,开始推演:

  • “1” :返回1,解码方式只有“A”
  • “12” :返回2,解码方式有“AB”(1 2),“L”(12)
  • “122” :返回3,解码方式有“ABB”(1 2 2),“LB”(12 2),“AV”(1 22)
  • “1221” :返回5,解码方式有“ABBA”(1 2 2 1),“LBA”(12,2,1),“AVA”(1,22,1),“ABU”(1,2,21),“LU”(12,21)

当时我自己做的时候,想到的输入是"12213",推过之后才发现了规律,可能比较笨。。。

光看前2个输入可能看不出什么。

  • 看输入为“122”的时候,比原先的输入“12”新增加了一个‘2’,看看增加后相对于原来“12”的输入,解码方式的总数是怎么发生改变的。

    增加了‘2’之后,从原先的2种方式变到3种方式。

    前两种方式“ABB”(1 2 2),“LB”(12 2)都是在原本“AB”(1 2),“L”(12)的基础上增加了一个解码'2'得到大写字母‘B',并没有增加解码方法。促使增加的原因是新增的'2'能与前一个位置的’2‘合并成'22',即解码成字母'V',因此多了新的一种解码方式“AV”。

    这样看来,后一个位置上的解码总数确实与之前位置的解码总数有一定的关系,现在还不能明确的说到底是如何。

  • 看第4组,在"122"的基础上增加了‘1’

    • 以之前的思路考虑,“122”原本的解码方式为“ABB”(1 2 2),“LB”(12 2),“AV”(1 22),新增了'1',如果不与前面位置的'2'合并的话,那么不增加解码总数,仍旧为3,解码方式变为“ABBA”(1 2 2 1),“LBA”(12,2,1),“AVA”(1,22,1);

    • 如果与前面位置的'2'绑定的话变成'21',解码为‘U’,现在后两个数已经绑定了,也就是问输入“12(21)”有几种方式,因为解码的方式只可能是数字两位数[1-26],所以‘21’不可能与前面位置的‘2’绑定,这么看来,“12(21)”的解码总数与“12”的解码总数无异。

    而“12”的解码总数之前是有记录过的,“AB”(1 2),“L”(12),加上‘U'后变为“ABU”(1,2,21),“LU”(12,21)。

    所以看来输入为“1221” 时,解码方式有“ABBA”(1 2 2 1),“LBA”(12,2,1),“AVA”(1,22,1),“ABU”(1,2,21),“LU”(12,21),一共有5种。假设当前位置为i,那么如果位置i的数字能与位置i-1的数字合法绑定[10-26]的话。

    dp[i] = dp[i-1] + dp[i-2]; dp[i]代表位置i的解码总数

  • 说到合法绑定,假如我的输入是“1228”,显然,“28”不是合法的,不能被解码。那么解码总数应该就等于“122”的解码总数。可以自行推演一下。

现在总结字符串无0输入是的状态转移方程:

# 位置i的解码总数为dp[i]
if 位置i 与 位置i-1 能合法绑定:
    dp[i] = dp[i-1] + dp[i-2];
else
    dp[i] = dp[i-1]

关于0

一开始我以为输入"01"是合法的,因为我觉得可以解码成'A'。后来提交后报错,我才意识到想当然了。当位置i出现'0'时,一定要考究i-1位置上的字符,下面举几个例子:

  1. '10' - 输入是合法的,因为0可以和前面的1绑定在一起,得到10,解码为"J",返回值为1
  2. '100' - 输入不合法,无法解码,无论是(1 0 0)(1 00)(10 0)(100)都是不合法的,返回为0
  3. '01' - 输入不合法,无法解码,这正是我之前想当然所犯的错误

有0输入情况

  1. 如果0在第一个输入,由于0无法被解码,所以返回解码总数0.
  2. 连续两个00出现肯定无法被解码,所以返回解码总数0
  3. 当前位置i出现0,必须要与i-1位置的数绑定,绑定不成功,返回0;绑定成功,位置i的解码总数与位置i-2相同。这个推导其实在上面绿字部分出现过,可以回去看看理解下。

代码

class Solution {
public:
    int numDecodings(string s) {
        // 边界条件:s为空;第一个输入为0;输入字符串长度为1
        if(s.size() == 0 || s[0] == '0')
            return 0;
        if(s.size() == 1)
            return 1;

        // parameters
        int len = s.size();
        int dp[len];
        dp[0] = 1;

        // 考虑第2个位置的解码总数的可能情况
        if(s[1] == '0' && (s[0] - '0') * 10 > 20)
            return 0;
        else if(s[1] == '0' && (s[0] - '0') * 10 <= 20)
            dp[1] = 1;
        else if(s[1] != '0' && (s[0] - '0') * 10 + s[1] - '0' > 26)
            dp[1] = 1;
        else
            dp[1] = 2;

        for(int i = 2; i < len; i++)
        {
            //判断的情况颇多,但是最重要的是当出现0时,它能否与前面出现的数字绑定为一个[1,26]内的合法数字,如果不能,返回0;否则,等于dp[i-2]

            //出现连续2次的0,直接返回0
            if(s[i] == '0' && s[i-1] == '0')
                return 0;

            else if(s[i] == '0' && s[i-1] != '0')
            {
                int t = (s[i-1] - '0') * 10;
                if(t > 20)                  // 不能绑定,直接返回
                    return 0;
                else                         // 可以绑定
                    dp[i] = dp[i-2];
            }

            else if(s[i] != '0' && s[i-1] != '0')
            {
                int t = (s[i-1] - '0') * 10 + s[i] - '0';
                if(t > 26)
                    dp[i] = dp[i-1];        // 不能绑定,等于前面位置
                else
                    dp[i] = dp[i-1] + dp[i-2];
            }
            else if(s[i] != '0' && s[i-1] == '0')
                dp[i] = dp[i-1];
        }

        return dp[len-1];
    }
};

总结

需要考虑很多的边界条件。

01-20 13:53