LeetCode Q91: 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.

Solution:

Dynamic programming. Given current character s[i], the number of possible decode ways for string after s[i] is composed of two parts:

1. s[i+1 : end].

2. s[i+2 : end], if substring s[i : i+1] <= 26.

The trick part of this question are cases when there are '0's in the string. Then, when current character s[i]==0, the number of decode ways for string after s[i] is 0. When s[i+1] is '0', we count it as qualified decode.