## Number of ways decoding a message (Decode Ways)

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12” is 2.

Thoughts:
Again, we can use recursion with backtracking. Each time we try to encode the first digit in the message to a letter, or we can encode the first two digits into a letter if possible, we then recursively do the samething for the sub-string. When there is no way to encode (e.g., encountering a single ‘0’, or encountering ’32’ and tyring to encode the two-digits to a letter), we simply return. If there is no sub-string to go on, we know we have found a valid solution, so we increase the count.

Code (C++):

```class Solution {
public:
int numDecodings(string s) {
int solutions = 0;
if(s.size() != 0)
recursion(s, solutions);
return solutions;
}

void recursion(string s,int &solutions) {
if(s.size() == 0){
solutions++;
} else {
int value = (int)s.at(0)- '0';
if(value > 0 && value <= 9) {
recursion(s.substr(1), solutions);
}

if(s.size() >= 2) {
int value1 = (int)s.at(0) - '0';
int value2 = (int)s.at(1) - '0';
if(value1 == 1 && value2 >= 0 && value2 <= 9) {
recursion(s.substr(2), solutions);
} else if(value1 == 2 && value2 >= 0 && value2 <= 6) {
recursion(s.substr(2), solutions);
}
}
}
}
};

Code (Java):
This is a very werid way to do it, I know. The ArrayList solutions are pretty much useless there other than counting the number of valid solutions. It’s just a way to bypass the fact that Java cannot pass argument by reference.
import java.util.ArrayList;
public class Solution {
public int numDecodings(String s) {
ArrayList<Integer> solutions = new ArrayList<Integer>();
if(s.length() != 0)
recursion(s, solutions);
return solutions.size();
}

private void recursion(String s, ArrayList<Integer> solutions) {
if(s.length() == 0){
} else {
int value = Character.getNumericValue(s.charAt(0));
if(value > 0 && value <= 9) {
recursion(s.substring(1), solutions);
}

if(s.length() >= 2) {
int value1 = Character.getNumericValue(s.charAt(0));
int value2 = Character.getNumericValue(s.charAt(1));
if(value1 == 1 && value2 >= 0 && value2 <= 9) {
recursion(s.substring(2), solutions);
} else if(value1 == 2 && value2 >= 0 && value2 <= 6) {
recursion(s.substring(2), solutions);
}
}
}
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c9102a9e13a0', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c9102a9e13c9',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c9102a9e13ca',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```

1. itnovice
Jul 18, 2012 @ 21:48:12

I think you can wrap the integer in a class and class object will be pass by reference.

• No it won’t. You can try it.

2. This recursion method you provided is very neat and clean. But it might not be very efficient due to numerous recursive calls. I was wondering if it is able to pass the Large test case of leetcode online judge?
Thanks for sharing your idea. It is brilliant.
P.S. I think you actually CAN wrap the integer as class data member. It tried and it worked.

3. A typo: I tried and it worked. ๐

• ๐

4. Baiyang
Dec 17, 2012 @ 19:01:48

Accidentally found your blog. Nice work!

I used to have dp for this.
public class Solution {
public int numDecodings(String s) {
// Start typing your Java solution below
// DO NOT write main() function
int n = s.length();
if(n==0) return 0;
int[] ways = new int[n+1];
ways[0] = 1;
for(int i = 0; i 0) ways[i+1] += ways[i];

if( i > 0)
{
int val2 = (s.charAt(i-1)-‘0’)*10 + val;
if (val2 >= 10 && val2 <= 26)
ways[i+1] += ways[i-1];
}
}
return ways[n];
}
}

• Elegant!

5. Neil Liang
Feb 03, 2013 @ 16:57:41

This code is neat. But I got time-exceed for the large test. Maybe a DP solution would work