Question :
Number of Decodings
Consider the following encoding scheme,
A->1, B->2,..., Z->26
Given an encoding using this scheme (a string containing at most 1000 digits),
find the number of possible decodings.
The function should return a string containing the number of decodings.
Note: The input string contains valid digits from 0 to 9 and there are no leading O's, no extra
trailing O's and no two or more consecutive O's.
Input Specification:
input1: the input string
Output Specification:
Return a string representing the number of possible decodings
phim
Answers
Explanation:
this is the ans so enjoy it
Answer:
Explanation:
Given a positive number, map its digits to the corresponding alphabet in the mapping table [(1, 'A'), (2, 'B'), … (26, 'Z')], and return the count of the total number of decodings possible. Assume that the input number can be split into valid single-digit or two-digit numbers that are present in the mapping table.
For example,
Input: 123
Output: 3
The possible decodings are [ABC, AW, LC]
Input: 1221
Output: 5
The possible decodings are [ABBA, ABU, AVA, LBA, LU]
Practice this problem
From the above examples, it is evident that,
A single digit between 1–9 can be mapped to a corresponding alphabet between A–I.
Two digits between 10–26 can be mapped to a corresponding alphabet between J–Z.
So, the problem of computing T(n) for an n–digit number can be broken down into the subproblems of computing T(n-1) if the last digit lies between 1–9 and computing T(n-2) if the last two digits lie between 10–26, and finally adding the two.
The algorithm can be implemented as follows in C++, Java, and Python:
#include <iostream>
#include <string>
using namespace std;
// Function to count the total decodings of a given sequence of digits
int count(string seq, int n)
{
// base case
if (n == 0 || n == 1) {
return 1;
}
int sum = 0;
// consider single-digit numbers (1, 2, … 8, 9)
if (seq[n - 1] >= '1' && seq[n - 1] <= '9') {
sum = count(seq, n - 1);
}
// consider 2-digit numbers (10, 11, … 19, 20, … 25, 26)
if (seq[n - 2] == '1' || (seq[n - 2] == '2' && seq[n - 1] <= '6')) {
sum += count(seq, n - 2);
}
return sum;
}
int main()
{
int x = 1221;
string seq = to_string(x);
cout << "The total number of decodings are " << count(seq, seq.length()) << endl;
return 0;
}