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 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).

The solution is very simple.

We shall take 2 variables “r1” and “r2” to store the last and last of the last value.

Then we check if the number is a 2 digit letter, then new r1 is sum of both while new r2 is the old r1.

Then if it is a one-digit letter, no new way added.

/*
* File     : Decode_ways.cpp
*/ 


#include<iostream>
#include<string>

using namespace std;

int numDecodings(string s) {
    // empty string or leading zero means no way
    if (!s.size() || s.front() == '0') return 0;

    // r1 and r2 store ways of the last and the last of the last
    int r1 = 1, r2 = 1;

    for (int i = 1; i < s.size(); i++) {

        // zero voids ways of the last because zero cannot be used separately
        if (s[i] == '0') r1 = 0;
        
        // possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
        if ((s[i - 1] == '1' || s[i - 1] == '2') && s[i] <= '6') 
        {
            r1 = r2 + r1;
            r2 = r1 - r2;
        }

        // one-digit letter, no new way added
        else 
        {
            r2 = r1;
        }
    }

    return r1;
}


int main()
{
    string str = "226";
    cout<<"The number of ways to decode the string " << str << " is = "<< numDecodings(str)<<endl;
}

Output:

The number of ways to decode the string 226 is = 3