3
\$\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 the following recursive 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\$
1
\$\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\$
1
\$\begingroup\$

To me, the code does not express the solution in a way that is easily connected to the description of the problem. "Message" becomes data. It's not really clear to me how "number of ways" is represented in the code except as the ultimate return value.

Business Logic

Deeper down, the code does not reflect the way I reason through the examples. I understand

"12" -> 2
"226" -> 3

imply that "one followed by any number" and "two followed by 0,1,2,3,4,5, or 6" can be interpreted two ways.

Pseudo-code that looks more like the business logic to me:

// if all characters are not digits, 
// there are zero ways to interpret the message
if not Message.allDigits() return 0

// if the message is only zeros, 
// there are zero ways to interpret the message
if Message.allDigitsAreZero() return 0

// otherwise there is at least one way to interpret it
ways = 1

//using one based index for simplicty
For i from 0 to Message.length
  case
    i equals Message.length() {
      return ways
    Message.charAt(i) is '0'
      i++
    Message.charAt(i) is '1' 
      ways += 1
      i++
    Message.charAt(i) is '2' 
      AND Message.charAt(i+1) is '[0-6]'
        ways += 1
         i++
  end case

Pseudo-Code as a specification

The pseudo-code defines a solution shape that is more independent of the language used to implement it. It reflects the problem and not the language we use to implement it.

Validation suggests an implementation approach

Starting with data validation (allDigits and allDigitsZero) on the whole message suggests regex's -- anything else is more work to implement.

allDigits(Message)
  Message.matches("\d{" + string.length + "}")

allDigitsZero(Message)
  Message.matches("0{" + string.length + "}")

Using regexes the rule for 1 might look like:

 // One indexing is messy here.
 // Zero indexing would be cleaner
 Message.matches(".{" + i-1 + "}1\d*")
      ways += 1
      i++

Implementation approach suggests an architecture

But that's a bit less readable than I want to try to figure out six weeks from now. This is a case where recursion can help make the code more readable assuming the reader can read recursion.

// overloading decode
int decode(Message, ways)
  case
    Message.length equals 1
     return ways
    Message.matches("1\d*)"
      decode(Message.substring(2), ways+1) // one indexed
    Message.matches("2[0-6]")
      decode(Message.substring(2), ways+1) // one indexed
    decode(Message.substring(2), ways+1) // one indexed
  end case

Discussion

Is this more efficient? Without profiling running code in a production environment, there's no way to tell. The JVM performs more optimizations than most people can readily reason about. Plus there's no way to tell if more efficiency here matters. If the messages are being read from disk, or coming from the internet, or even read from RAM, decode probably isn't the bottle neck. And the system is almost certainly running other code.

Is it better? Maybe. Maybe not. In Java, Loops are idiomatic. Recursion not so much. If other parts of the system are recursive then recursive code is more consistent with the rest of the code base. If it's the only piece of recursive code, then recursion might not be the better choice.

One way in which a regex approach might be better is that it does not require changing the data type. We get a string and operate on it as a string. Recursion using substring makes the code less complex (again, assuming the people reading it can readily read recursion).

One way in which a regex approach might be worse is that pattern matching is not a primary Java idiom. It's mostly reserved for strings. Other languages use it more extensively. But we start with a string, so it's more likely ok.

Final thoughts

  • Better names
  • Logic that looks like the business problem
  • Comments, please
\$\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.