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