Print all possible codes for a given string

Question

My question is to print all possible codes for the string.

Assume that value of a=1, b=2, c=3, d=4, .... z=26.

E.g. for “1123” possible codes are aabc, kbc, alc, aaw, kw

Here's what I could come up with.

   private static void printCodes(String str, String ans) {
    if (str.length() == 0) {
        System.out.println(ans);
        return;
    }

    String ch1 = str.substring(0, 1);
    String restOfTheString1 = str.substring(1);

    if (Integer.parseInt(ch1, 10) > 0) {
        char code = (char) (Integer.parseInt(ch1, 10) + 'a' - 1);
        printCodes(restOfTheString1, ans + code);
    }

    if (str.length() >= 2) {
        String ch12 = str.substring(0, 2);
        String ros2 = str.substring(2);

        if (Integer.parseInt(ch12, 10) > 0 && Integer.parseInt(ch12) <= 26) {
            char code = (char) (Integer.parseInt(ch12, 10) + 'a' - 1);
            printCodes(ros2, ans + code);
        }
        if (Integer.parseInt(ch12, 10) == 0) {
            printCodes(ros2, ans);
        }
    }
}

Let me know if I did something wrong or anything could have been better. Thanks!

Answer 1

Your code is a reasonably neat use of recursion to solve the problem, and recursion is a good solution to this problem. I prefer it for people to make it obvious that a function is used recursively to prepare myself for what to expect, I tend to use "recursive" in the name. You don't show how you set up the recursive method, though, and in general it's poor form to embed print statements inside functions that do other things too (single responsibility principle: https://en.wikipedia.org/wiki/Single_responsibility_principle).

A better solution would be to return a collection of results that you can print in a separate place.

What really bothers me, though, is two things:

• the hard-coded assumption that all codes are either 1 or 2 characters/digits. I realize that in your input problem it's true, but I feel there's a better way, or a more general way to solve this problem
• the conversion to integers, and integer parsing of strings

Personally I am not too concerned about the string-concatenation you use for computing the ans value when recursing, but there may be a better way with using a pre-computed array, with tracking indices. I would consider the array/index solution a "phase 2" thing if performance is an actual, proven problem.

So, having said the above, it's best to explain it with code... I would do two significantly different things... I would set up a lookup table of string-based "digit" keys, and the corresponding character value. I would then loop through that table in the recursive function to determine the matches....

Setting up the table is relatively complicated, but it's a 1-time thing consisting of 2 correlated string arrays:

private static final String[] keys;
private static final String[] values;

static {
    String alphabet = "abcdefghijklmnopqrstuvwxyz";
    keys = new String[alphabet.length()];
    values = new String[alphabet.length()];
    for (int i = 0; i < alphabet.length(); i++) {
        keys[i] = String.valueOf(i + 1);
        values[i] = alphabet.substring(i, i + 1);
    }
}

Now, with those two arrays, we can decode the values "easily":

public static List<String> decode(String input) {
    List<String> results = new ArrayList<>();
    decodeRecursive(input, "", results);
    return results;
}

private static void decodeRecursive(String input, String current, List<String>results) {
    if (input.length() == 0) {
        results.add(current);
        return;
    }

    for (int i = 0; i < keys.length; i++) {
        String key = keys[i];
        if (input.startsWith(key)) {
            decodeRecursive(input.substring(key.length()), current + values[i], results);
        }
    }
}

Note that all the work is basically in the "string" space, and not parsing integers, etc. Also, the presentation/printing is done somewhere else.

I put this together in a program on ideone so you can see it working: https://ideone.com/sozgXb

Answer 2

Consider

    private static void printCodes(String str, String ans) {
        if (str.length() == 0) {
            System.out.println(ans);
            return;
        }

        char ch1 = str.charAt(0);
        char code = (char) (ch1 - '1' + 'a');
        printCodes(str.substring(1), ans + code);

        if (str.length() >= 2 && ch1 <= '2') {
            int i = Integer.parseInt(str.substring(0, 2), 10);
            if (i > 0 && i <= 26) {
                code = (char) (i + 'a' - 1);
                printCodes(str.substring(2), ans + code);
            }
        }
    }

Rather than work with a String just work with characters when you can. Working with a String for the two characters is making use of the algorithm. For a single character? It's just the long way around.

I prefer not to use intermediate variables for single uses, particularly if they don't have good names.

I do like using intermediate variables (e.g. i) if the value are used multiple times.

We do not need to handle the case when the parsed value is zero. The string is malformed in that case, so the value won't be correct. So we might as well not bother.