current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question
    
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 at 2:21

2 Answers 2

up vote 1 down vote

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.

Reusing your exemples and adding more :

  • 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.

share|improve this answer
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.