‘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**.