# Given a digit sequence, print the possible decodings of the given digit sequence

Examples:

12 gives:

'AB' and 'L'

and

123 gives

'ABC', 'LC' and 'AW'

Here is my attempt:

import java.util.*;

public class decoding {

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");
codes.put(5, "E");
codes.put(6, "F");
codes.put(7, "G");
codes.put(8, "H");
codes.put(9, "I");
codes.put(10, "J");
codes.put(11, "K");
codes.put(12, "L");
codes.put(13, "M");
codes.put(14, "N");
codes.put(15, "O");
codes.put(16, "P");
codes.put(17, "Q");
codes.put(18, "R");
codes.put(19, "S");
codes.put(20, "T");
codes.put(21, "U");
codes.put(22, "V");
codes.put(23, "W");
codes.put(24, "X");
codes.put(25, "Y");
codes.put(26, "Z");
}

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

construct();

int n = str.length();

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

// 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;

String x = codes.get(Integer.parseInt(str.substring(0, 1)));
if (x == null)
return;
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;

String y = codes.get(Integer.parseInt(str.substring(0, 2)));

decode(str.substring(2), built+y);
}
}

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


I haven't done any memoization or dynamic programming in this. It's a rather crude solution with exponential run time I believe. Let me know what you think.

• Welcome to Code Review! I feel sure there is a more elegant way of coming to this solution, I hope you get some good reviews! – Phrancis Feb 11 '15 at 2:21

A few hints :

• compile your code with all warning enabled (calls doesn't seem to be used, does it ?)

• write your code in such a way that it can easily be tested. This includes taking a well-defined input and returning a well-defined value (instead of printing it).

• write tests.

An example of dynamic programming approach (but I do think it will be better for you if you try to rewrite your solution with tests first, at least you'll be able to compare results and performance): asuming you have a string s "dddddD1D2" (a string composed of any digits then digit D1 then digit D2) and you know the number of combinations for all strings "" (empty string), "d", "dd", "ddd", ..., "ddddddD1", how to you know the number of combinations for string s ?

You have two different options :

• either D2 is to be converted on its own (if D2 is positive). So if D2 is positive, you have as many combinations like this one as you have combinations for "ddddddD1" which is a known value.

• either D2 is to be converted with previous digit D1. This is possible if 1 <= 10*D1 + D2 <= 26. If it is the case, you have as many combinations as the number of combinations for "dddddd" which is a known value.

Well, I gave you a solution assuming you had a solution. How do you get such a thing working ? You just need to iterate over the string and for each string position, you keep track of the number of combinations that can be generated using characters up to that point :

• 0 character : 1 combination
• 1 character : it has to be converted on its own. Reuse the solution for 0 characters.
• 2 characters : reuse the solution for 0 and 1 characters
• n characters : reuse the solution for n-2 and n-1 characters.

This is a classic example of algorithm where we can define the number of elements with a property without having to enumerate them.

You can either save the two last results as you progress or you can keep track of the result for each index in an array. This is up to you.

• nb("") = 1
• nb("1") = nb("") = 1
• nb("12") = nb("1") + nb("") = 1 + 1 = 2
• nb("123") = nb("12") + nb("1") = 1 + 2 = 3
• nb("1234") = nb("123") = 3 because 34 cannot be converted to a letter.

Disclaimer : I haven't tried any of this but I think it kind of makes sense. You'll see if it works as you write tests and compare with the results from your current code.

• 2 years late, but thank you for your input :) I read it when you posted in 2015. – Siddhartha Oct 31 '17 at 17:44

You haven't written any unit tests, the output to system.out.println at the bottom of the recursion shows this. This is a concern because any changes you make could break the program and you might not notice.

To fix the testability issue you could move decode to an object of its own and have it accumulate the result strings in a list. This list could be printed out from main, or validated by unit tests.