0
\$\begingroup\$

I am working on problem where I need to decode a string..

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1

'B' -> 2

...

'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"

Output: 2

Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"

Output: 3

Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

I came up with below recursion approach and it works fine. Is there any better or efficient way to solve the same problem?

  public static int decode(String data) {
    int[] memo = new int[data.length() + 1];
    return helper(data, data.length(), memo);
  }

  private static int helper(String data, int k, int[] memo) {
    if (k == 0)
      return 1;
    int s = data.length() - k;
    if (data.charAt(s) == '0')
      return 0;
    if (memo[k] != 0) {
      return memo[k];
    }

    int result = helper(data, k - 1, memo);
    if (k >= 2 && Integer.parseInt(data.substring(data.length() - k, data.length() - k + 2)) <= 26) {
      result += helper(data, k - 2, memo);
    }
    memo[k] = result;
    return result;
  }
\$\endgroup\$
0
\$\begingroup\$

First off, as mentioned in the comments the variable and function name(s) could be a bit more descriptive. decode is fine, but helper should be renamed to something like count_decodings. k could be len or substring_length. I disagree with the comments about data though- we know nothing about the string being passed, so the only more apt name would be lowercase string, which at first glance may get confused with the type.

Moving on to structure, you can actually revise your algorithm to do away with k, and make the substring logic simpler. Assume the string that is passed is the entire string- no offset. Then call your function recursively on a substring of the input string.

private static int helper(String data, int[] memo) {
    if (data.length() == 0)
        return 1;
    if (data.charAt(0) == '0')
        return 0;
    if (memo[data.length()] != 0) {
        return memo[data.length()];
    }

    int result = helper(data.substring(1), memo);
    if (data.length() > 1 && Integer.parseInt(data.substring(0, 2)) <= 26) {
       result += helper(data.substring(2), memo);
    }
    memo[data.length()] = result;
    return result;
}

As you can see, this results in far less index juggling, and is far easier for someone else to read. When I was writing this answer there were at least two other answers trying to figure out the correct way to juggle these indices to make the algorithm work, and both were since deleted by their authors because they were too error prone / couldn't get it working quite right. If that doesn't say something about the maintainability and readability of index juggling, I don't know what does.

Lastly, I'd like to speculate that the algorithm could possibly be sped up by minimizing the conversions between strings and integers. You could possibly replace

data.substring(0, 2)) <= 26

with

data.substring(0, 2).compareTo("26") < 1

-which would save the conversion, but at the cost of confusion and bad form (comparing numerical values as strings). Alternatively, you could convert data to an integer once, and then do floored division and modular reduction by 10 to get your digits and "substrings". These would only provide constant speedups at best, however.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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