[leetcode] 91. Decode Ways

一时失言乱红尘 2022-06-13 03:27 99阅读 0赞

**91. Decode Ways**  
A message containing letters from A-Z is being encoded to numbers using the following mapping:  
**‘A’ -> 1**  
**‘B’ -> 2**

**… …**

**‘Z’ -> 26**  
Given an encoded message containing digits, determine the total number of ways to decode it.  
For example,  
Given encoded message **“12”**, it could be decoded as **“AB”**(1 2) or **“L”**(12).  
The number of ways decoding **“12”** is 2.

一条信息是由26个英文字母组成的，如果分别将字母与数字对应起来，如下：  
**‘A’ -> 1**  
**‘B’ -> 2**

**… …**

**‘Z’ -> 26**  
那么给定一个数字，可有有多少种信息编写的可能性。  
例如：  
给定一个数字12，该数字可以代表AB，或者L。  
因此数字12有2种编写的可能性。

**解题思路**  
这是一道动态规划的问题。  
我们需要考察输入数字串中第i，i-1，i-2三个字符。  
设decode\_ways\[i\]为到第i个字符为止，找到的解码个数，s\[i\]为输入串中第i个字符。那么s\[i-1\]和s\[i\]可以有几种可能：  
1、s\[i\]，s\[i-1\]分别可以解码，同时s\[i-1\]s\[i\]组成的二位数也可以解码。这样，decode\_ways\[i\]应该是decode\_ways\[i-1\]和decode\_ways\[i-2\]的和。例如”221”，解码的数字等于”22“解码的数字（多余的1可以单独解码）与”2“解码的数字（多余的”21“也可以单独解码）之和。  
2、s\[i\]不能单独解码（为0），那么必须和s\[i-1\]组成一个部分，decode\_ways\[i\]只能等于decode\_ways\[i-2\]。  
3、s\[i-1\]s\[i\]不能解码，但是s\[i\]可以解码。那么decode\_ways\[i-2\]将无法贡献，解码的数字decode\_ways\[i\]等于decode\_ways\[i-1\]。  
4、其他情况（包括几种不可能存在的情况，如s\[i-1\]s\[i\]可以解码但是s\[i\]，s\[i-1\]都不可以解码），decode\_ways\[i\]只能等于0。

代码实现如下：

class Solution  
    {  
    public:  
        bool two_valid(char c, char d)  
        {  
            return c!=0 && c*10+d<=26;  
        }  
    
        int numDecodings(string s)  
        {  
            const int LEN=s.size();  
    
            if (LEN==0 || s[0]=='0') return 0;  
            if (LEN==1) return 1;  
            transform(s.begin(), s.end(), s.begin(), bind2nd(minus<char>(),'0'));  
            vector<int> decoding(LEN);  
            vector<int> valid(LEN);  
            transform(s.begin(), s.end(), valid.begin(), bind2nd(not_equal_to<char>(), 0));  
    
            decoding[0]=valid[0];  
            if (two_valid(s[0],s[1]))  
                decoding[1]=(valid[1] ? decoding[0]+1 : decoding[0]);  
            else  
                decoding[1]=(valid[1] ? 1 : 0);  
    
            for(int i=2;i<LEN;++i)  
            {  
                int k=(valid[i]<<2)+(valid[i-1]<<1)+two_valid(s[i-1],s[i]);  
                switch(k)  
                {  
                    case 7:  
                        decoding[i]=decoding[i-2]+decoding[i-1];  
                        break;  
                    case 3:  
                        decoding[i]=decoding[i-2];  
                        break;  
                    case 4:  
                    case 6:  
                        decoding[i]=decoding[i-1];  
                        break;  
                    default:  
                        decoding[i]=0;  
                        break;  
                }  
            }  
            return decoding[LEN-1];  
        }  
    };

代码实现2

class Solution {
    public:
        int numDecodings(const string &s) 
        {
            if (s.empty() || s[0] == '0') return 0;
            int prev = 0;
            int cur = 1;
            // 长度为 n 的字符串，有 n+1 个阶梯
            for(size_t i = 1; i <= s.size(); ++i) 
            {
                if (s[i-1] == '0') cur = 0;
                if (i < 2 || !(s[i - 2] == '1' ||(s[i - 2] == '2' && s[i - 1] <= '6')))
                    prev = 0;
                int tmp = cur;
                cur = prev + cur;
                prev = tmp;
            }
            return cur;
        }
    };