you are given a string having digits, convert into the string by looking at the table given below, solution in C++

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

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

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.

Solution in C++

#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

The above solution is O(1) space and O(n) time.

List Of Tutorials available in this website: