CODEWITHSUNDEEP
javaalgorithmrecursiondynamic-programming
Siddhartha
Siddhartha

Reputation: 4464

Converting a rudimentary recursive algorithm to a dynamic bottom-up tabulation algorithm

The problem statement: Given a digit sequence, count the possible decodings of the given digit sequence.

Examples:

12 gives 2 for:

'AB' and 'L'

and

123 gives 3 for:

'ABC', 'LC' and 'AW'

Here is my attempt:

import java.util.*;

public class decodingcount {

static int calls = 0;    
static Map<Integer, String> codes  = new HashMap<Integer, String>();

private static void construct(){
codes.put(1, "A");
codes.put(2, "B");
codes.put(3, "C");
codes.put(4, "D");
//..so on
}

private static int decode(String str, String built){

    construct();        

    int n = str.length();
    int count = 0;

    if (n == 0) {
        System.out.println(built);
        return 1;
    }

        // If you have 0's, then they don't have a corresponding singular letter. Break off the recursion.
        if (str.substring(0, 1).equals("0"))
            return 0;

        String x = codes.get(Integer.parseInt(str.substring(0, 1)));
        
        if (x == null)
            return 0;

        count = decode(str.substring(1), built+x);

        if (n > 1) {
            
            // If it's more than 26, it doesn't have a corresponding letter. Break off the recursion.
            if (Integer.parseInt(str.substring(0, 2)) > 26)
                return 0;

            String y = codes.get(Integer.parseInt(str.substring(0, 2)));
            
            count += decode(str.substring(2), built+y);
        }

        return count;
    }

    public static void main(String[] args) {
    System.out.println(decode(args[0], ""));
        }
    }

This runs in exponential time. I'm really struggling to convert this into a dynamic programming bottom-up tabulation algorithm. Here is my attempt .It returns 0. Would appreciate any help.

Upvotes: 3

Views: 319

Answers (1)

Pham Trung
Pham Trung

Reputation: 11294

Working code:

private static int decode(String str) {

    construct();

    int n = str.length();
    int[] count = new int[n];

    count[0] = 1;

    for (int i = 1; i < n; i++) {
        String x = codes.get(Integer.parseInt(str.substring(i, i + 1)));
        if (str.charAt(i) != '0')
            count[i] = count[i - 1];
        if (Integer.parseInt(str.substring(i - 1, i + 1)) <= 26 && str.charAt(i - 1) != '0')
            count[i] += (i - 2 >= 0 ?  count[i - 2] : 1);
    }

    return count[n - 1];

}

Upvotes: 3

Related Questions