# Decode Ways  Difficulty Level Medium
Dynamic Programming String

In Decode Ways problem we have given a non-empty string containing only digits, determine the total number of ways to decode it using the following mapping:

```'A' -> 1

'B' -> 2

...

'Z' -> 26```

## Example  S = “123”

Number of ways to decode this string is 3 If we look closely at the problem then we can observe that all the one-digit number except 0 are valid but in case of two-digit number only numbers from 10 to 26 are valid.

Hence we can conclude that at every index we have two steps:

1. If the ith element of a string is not ‘0’ then we have one way to decode the string starting with ith index using the mapping:

```'A' -> 1

'B' -> 2

….

'I' -> 9```

2. If we can merge the ith and (i+1)th index together to form a valid number using the following mapping:

```'J' -> 10

'K' -> 11

….

'Z' -> 26```

Then we have one more way to decode the string starting with ith index.

## Algorithm for Decode Ways  Step 1: Declare and initialize a 1D array of size n with zero.

Step 2: Check if we can decode the string which starts and ends both at (n-1)th index( Base case ).

Step 3: Run a loop and check at every step if we can use the ith index element as one digit valid number or merge it with (i+1)th index element to form a valid number of two digit.

1. If s[i]!=’0’, then dp[i]+=dp[i+1]
2. If s[i]==’1’, then dp[i]+=dp[i+2]
3. If s[i]==’2’ and s[i+1]<=’6’, then dp[i]+=dp[i+2]
Count Primes in Ranges

Step 4: Return dp.

## Implementation  ### C++ program for Decode Ways

```#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
int n=s.length();
int dp[n+1];
memset(dp,0,sizeof(dp));
dp[n]=1;
if(s[n-1]!='0'){       //if the last chararcter is not zero then we have one way to decode it
dp[n-1]=1;
}
for(int i=n-2;i>=0;i--){
if(s[i]!='0'){
dp[i]+=dp[i+1];
}
if(s[i]=='1'){
dp[i]+=dp[i+2];
}
if(s[i]=='2'){
if(s[i+1]<='6'){
dp[i]+=dp[i+2];
}
}
}
return dp;
}
int main(){
string s="452625";
cout<<"The number of ways to decode the given string is: "<<numDecodings(s);
}
```
`The number of ways to decode the given string is: 4`

### JAVA program for Decode Ways

```public class Main
{
public static int numDecodings(String s) {
int n=s.length();
int[] dp=new int[n+1];
dp[n]=1;
if(s.charAt(n-1)!='0'){       //if the last chararcter is not zero then we have one way to decode it
dp[n-1]=1;
}
for(int i=n-2;i>=0;i--){
dp[i]=0;
if(s.charAt(i)!='0'){
dp[i]+=dp[i+1];
}
if(s.charAt(i)=='1'){
dp[i]+=dp[i+2];
}
if(s.charAt(i)=='2'){
if(s.charAt(i+1)<='6'){
dp[i]+=dp[i+2];
}
}
}
return dp;
}
public static void main(String[] args) {
String s="23572";
System.out.println("The number of ways to decode the given string is: "+numDecodings(s));
}
}
```
`The number of ways to decode the given string is: 2`

## Complexity Analysis for Decode Ways  Time complexity: O(n) where n is the length of the given string.

We are traversing the given string only once hence the complexity is O(n)

Space complexity: O(n) because we store the number of ways at each step in dp array which leads us to linear space complexity.

References