LeetCode Decode Ways

Description

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.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Decode Ways
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;

class Solution {
public:
    int numDecodings(string s) {
        int size = s.size();
        vector<int> nums(size, 0);
        if(size<=0)
            return 0;
        
        if(s[0]=='0')
            return 0;
        else
            nums[0] = 1;
        
        if(size==1)
            return nums[size-1];
        
        if(s[1]=='0'){
            if(s[0] <= '2')
                nums[1] = 1;
            else
                return 0;
        }
        else{
            if(s[0] == '1') nums[1] = 2;
            if(s[0] == '2'){
                if(s[1] <= '6') 
                    nums[1]=2;
                else
                    nums[1] = 1;
            }
            if(s[0] >= '3') nums[1] = 1;
        }
        
        for(int i=2;i<size;i++){
            if(s[i] == '0'){
                nums[i] = nums[i-2];
                if(s[i-1] >= '3' || s[i-1] <= '0')
                    return 0;
            }
            else{
                if(s[i-1] == '1')
                    nums[i] = nums[i-1] + nums[i-2];
                else if(s[i-1] == '2') {
                    if(s[i] <= '6')
                        nums[i] = nums[i-1] + nums[i-2];
                    else
                        nums[i] = nums[i-1];
                }
                else{
                    nums[i] = nums[i-1];
                }
            }
        }
        return nums[size-1];
    }
};

Note

For the problem, note the zeros. If the current char is ‘0’, we need to verify whether it is valid or not. A vecotr nums is used to save the decode ways from the begin to the current char. If the current char can be a valid letter itself and also can join with the last char, then the decode ways of the current is nums[i-1] + nums[i-2].