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){
            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); 
                }
            }
        }
    }
}
Advertisements

8 Comments (+add yours?)

  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.

    Reply

  2. Jia
    Sep 26, 2012 @ 16:25:55

    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.

    Reply

  3. Jia
    Sep 26, 2012 @ 16:27:09

    A typo: I tried and it worked. ๐Ÿ˜›

    Reply

  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];
    }
    }

    Reply

  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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: