Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded

Question

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable. For example, '001' is not allowed.

class DailyCodingProblem7 {

    public static void main(String args[]) {
        String message = "11111111";
        int n=message.length();
        Integer[] ways=new Integer[n+1];
        int res = solution(message,n,ways);
        System.out.println(res);

    }

    private static int solution(String message,int k,Integer[] ways) {
        int n=message.length();
        if(k==0)
        {
            return 1;
        }
        if((int)message.charAt(n-k)==0)
        {
            return 0;
        }

        if(ways[k]!=null)
        {
            System.out.println(k+" : " +ways[k]);
            return ways[k];
        }
        ways[k]=solution(message,k-1,ways);
        if(k>=2 && Integer.valueOf(message.substring(n-k,n-k+2))<26)
        ways[k]+=solution(message,k-2,ways);
        return ways[k];

    }

}

If you observe the flow, we can notice ways[k] only needs the most recent 2 values this ways[k-1] and ways[k-2]. Should I use a Hashmap or there is a better approach?

1 : 1
2 : 2
3 : 3
4 : 5
5 : 8
6 : 13
34

Answer 1

Houston, you have some bugs

The algorithm counts incorrectly in some cases involving zeros. For example, there's only one way to make "10" or "20", not 2.

A different problem is the overly strict condition <26, which excludes "26" even it can be decoded to z.

Beware of string slicing

String.substring creates a new string. This could become expensive when repeated often. If you change the logic to work with a char[] instead of a String, then you can check if the first digit is '1', or the first digit is '2' and the second digit is <= '6'.

Unnecessary code

This condition will never be true:

if((int)message.charAt(n-k)==0)

The characters in the input are in the range of '0'..'9', therefore their int values are in the range of 48..57.

Unnecessary Integer[]

You could safely replace Integer[] with int[], and use a condition on zero value instead of null value.

Answer 2

You have almost understood the divide and conquer principle of recursion. Your solution is a bit too complex still.

1. For each mapping that matches the start of the sequence...
2. ...see how many times the rest of the sequence can be decoded.
3. If step 2 returned a number greater than 0, add the value to the sum.
4. Return sum.

The only thing you need to pass as parameters in the recursion is the sequence to be decoded and the index from which you start decoding.

As to code style, please read Oracles code conventions for Java

Ps. String.startsWith(prefix, offset) could be your friend right now.