A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: “12” Output: 2 Explanation: It could be decoded as “AB” (1 2) or “L” (12). Example 2:

Input: “226” Output: 3 Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Table of Contents

Thoughts

Maybe we just need to find how many ways are there to seperate the string legally into pieces of size 1 and size 2.
Since the solution need to be build up one by one instead of concurrently(like subset), we might need to use dynamic programming.
We build it from left to right; EG 12 is build upon from 1 and 123 is build upon 12.

DP

We use a DP array DP[i] to stores how many ways to decode numbers that are at nums[0:i]. And during the decoding, if we see invalid string, we will return 0.

Invalid result caused by 0

When ever we see a 0 that can’t be matched with the previous number, we know there is no way to decode the string so return 0. EG: 02; 200; In 02, the first 0 doesn’t have any previous number, in 200, the second 0 can’t match with 0 and form a valid number between [1,26].

Base case

DP[0] = 1

Recurrence

We have two big cases: s[i] == 0 and 1<=s[i] <=26

If s[i] == 0,

we need to match with the previous char s[i – 1]. If s[i-1]s[i] form a valid number, it will be the only way to keep sequence s[0:i] valid. So we have to take away s[i – 1] to form a valid number and that leave us with s[0:i-2] numbers to decode. So the number of ways to decode: DP[i] = DP[i – 2] . If we can’t match with s[i – 1], we return 0.

Else 1 <= s[i] <= 9

s[i] can itself be a stand alone number to be decoded. And it could also be combined with s[i – 1] if possible.
When it can only be standalone: eg s[i] = 9, s[i – 1] = 3, then the number of ways to decode s[0:1] is DP[i – 1] since it is the only way to decode s[i].
Think about it this way: if s[i] can only be standalone, then any way to decode s[0:i] will leave s[i] as a standalone. So decoding s[0:i] will be the same as decode s[0 : i – 1] then append s[i] at the end.

But if s[i] is a standalone and can form a valid number with s[i – 1], then the number of ways to decode s[i] will be the sum of
1. s[i] standalone, DP[i – 1]
2. s[i] matches with s[i -1], DP[i – 2]

So DP[i] = DP[i – 1] + DP[i – 2]

“`

“`c++

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty())return 0;
        vector<int>ways (s.size() + 1, 0);
        if(s[0] == '0')return 0;
        ways[0] = 1;
        ways[1] = 1;
        for(int i = 1; i < s.size() ;i ++){
            if(s[i] == '0'){
                if(s[i - 1] != '1' && s[i - 1] != '2') return 0;
                ways[i + 1] = ways[i - 1];  //0 is matched, we regress to 2 before
            }
            else{//s[i] b/t [1,9]
                //s[i] can form a new num with s[i - 1]
                if( s[i - 1] != '0' && (((int)s[i] - '0') + 10*((int)s[i - 1] - '0') <=26) ){
                    ways[i + 1] = ways[i]  + ways[i - 1];
                }
                else{
                    ways[i + 1] = ways[i];
                }
            }

        }
        return ways[s.size()];
    }
};

LC91. Decode Ways