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){
solutions.add(1);
} 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);
}
}
}
}
}

### Like this:

Like Loading...

*Related*

itnovice

Jul 18, 2012@ 21:48:12I think you can wrap the integer in a class and class object will be pass by reference.

Runhe Tian

Jul 19, 2012@ 00:03:09No it won’t. You can try it.

Jia

Sep 26, 2012@ 16:25:55This 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.

Jia

Sep 26, 2012@ 16:27:09A typo: I tried and it worked. ๐

Runhe Tian

Sep 26, 2012@ 16:31:08๐

Baiyang

Dec 17, 2012@ 19:01:48Accidentally 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];

}

}

Runhe Tian

Dec 17, 2012@ 21:02:06Elegant!

Neil Liang

Feb 03, 2013@ 16:57:41This code is neat. But I got time-exceed for the large test. Maybe a DP solution would work