decode ways

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.

my code:

package algorithm.weixin;

public class DecodeWays {

    public static final char[] CHARDICT = { '0', 'a', 'b', 'c', 'd', 'e', 'f',
                                            'g', 'h', 'i', 'j', 'k', 'l', 'm',
                                            'n', 'o', 'p', 'q', 'r', 's', 't',
                                            'u', 'v', 'w', 'x', 'y', 'z'};

    public static final int LEN = 27;
    public static int decodeWays( String s )
    {
        if( s == null || s.trim().length() == 0 )
        {
            return 0;
        }
        int ways = 1;
        char[] arr = s.toCharArray();
        ways = decodeWays( arr, 0, ways );
        //System.out.println( ways );
        return ways;
    }
    public static int decodeWays( char[] arr, int start, int ways )
    {
        if( start == arr.length - 1  )
        {
            return ways;
        }
        for( int i = start; i < arr.length -1 ; i++ )
        {
            if( ( getNumber( arr[i] )*10 + getNumber( arr[i+1] ) < 27 ) )
            {
                ways++;
                //System.out.println( ways );
                decodeWays( arr, i+2, ways );
            }
            else
            {
                decodeWays( arr, i+1, ways );
            }
        }
        return ways;
    }
    public static int getNumber( char c )
    {
        return c - '0';
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i = decodeWays( "11234" );
        System.out.println( i );
    }

}

Advertisements
This entry was posted in programming and tagged . Bookmark the permalink.

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