 # Number of ways to decode a message

## Problem Statement

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.

## Sample Test Cases

```Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
```

## Problem Solution

We will be using Dynamic Programming to solve this problem.

Let’s think of the sub problem. To decode a message of n characters, you need to know in how many ways you can decode message using n-1 characters and a message using n-2 characters.

Why are we going only two steps back ie n-1 and n-2 if we are calculating for n? Because the letter can be either represented by one character or a two characters.

So on each step keeping in mind the constraint that coding of letter is constrained between 1 and 26 we cascade through the array summing the values at n-1 and n-2.

## Complexity Analysis

Time Complexity: O(n) as we are traversing through the entire array once.

Space Complexity: O(n) we have to maintain the dp array which has same size as string.

## Code Implementation

```#include<bits/stdc++.h>
using namespace std;

int numDecodings(string s) {
vector<int>dp(s.size()+1,0);
dp=1;dp=1;
if(s=='0')return 0;
for(int i=2;i<=s.size();i++){
if(s[i-1]>'0')dp[i]=dp[i-1];
if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<'7'))dp[i]+=dp[i-2];
}
return dp[s.size()];
}
int main()
{
string s="226";
int x= numDecodings(s);
cout<<x;
}```

```public class Decode
{
public int numDecodings(String s)
{
if (s == null || s.length() == 0)
return 0;

int n = s.length();
int[] dp = new int[n + 1];
dp = 1;
dp = s.charAt(0) != '0' ? 1 : 0;

for (int i = 2; i <= n; i++)
{
int first = Integer.valueOf(s.substring(i - 1, i));
int second = Integer.valueOf(s.substring(i - 2, i));

if (first >= 1 && first <= 9)
dp[i] += dp[i-1];

if (second >= 10 && second <= 26)
dp[i] += dp[i-2];

}
return dp[n];
}

public static void main(String[] args)
{
Decode d = new Decode();
String s = "226";
System.out.println(d.numDecodings(s));

}

}```

```def numDecodings(s):
if not s or s == '0':
return 0

prev, curr = 1, 1
for i in range(1,len(s)):

if s[i] == '0':
curr = 0

if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
tmp = curr
curr += prev
prev = tmp

else:
prev = curr
return curr

print(numDecodings("226"))```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]