91. Decode Ways

/**

 * 91. Decode Ways

 * A message containing letters from A-Z can be encoded into numbers using the following mapping:

 * ‘A’ -> “1”

 * ‘B’ -> “2”

 * …

 * ‘Z’ -> “26”

 * To decode an encoded message, all the digits must be mapped back into letters using the reverse of the mapping above

 * (there may be multiple ways). For example, “111” can have each of its “1”s be mapped into ‘A’s to make “AAA”,

 * or it could be mapped to “11” and “1” (‘K’ and ‘A’ respectively) to make “KA”.

 * Note that “06” cannot be mapped into ‘F’ since “6” is different from “06”.

 * Given a string s containing only digits, return the number of ways to decode it.

 * The answer is guaranteed to fit in a 32-bit integer.

 * Example 1:

 * Input: s = “12”

 * Output: 2

 * Explanation: “12” could be decoded as “AB” (1 2) or “L” (12).

 * the O(n) solution below while simple is hard to think about

 * easier approach is via recursion but problem with that is it times out on leet code

 */

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/DecodeWays.java

The problem is asking for number of ways to decode a string. The complication arises from:

1. There is no decoding for 0
2. Number such as 111, can be decoded as AAA (via 1,1,1), AK via (1,11), or KA via (11,1)

Another way of thinking about the question is to think about number of paths that you can take to reach the end of the string with valid decodings.  This can be translated into a simple recursive traversal.

The algo is:

1. Each index we check whether value is 0, return 0
2. Check you reached the end of the string, since reaching the end signifies a valid combination you return a 1.
3. If you reach the last character in string, you return 1 since this is valid as well.
4. Each index, you traverse one forward.
5. If the next two chars as converted to integer within 10 & 26, you traverse two indexes ahead. Otherwise, don’t move two indexes ahead. This is because characters beyond 26 don’t have a valid conversion.

Here is the code for the solution:

public int numDecodings(String s) {
    if (s== null || s.isEmpty()) {
        return  0;
    }
    int twoBack = 1; //initialize two back to 1
    int oneBack = 0; //initialize one back to 0 or 1 depending on first index
    if (s.charAt(0) != '0') {
        oneBack = 1;
    }
    //loop to end index while looking at one and two before.
    //add one or two before to current index depending on whether they classify
    for (int i =2 ; i <= s.length(); i++ ) {
        int v=0;
        //add prior count if prior is not 0; you cant move from 0 one forward
        if (s.charAt(i-1) != '0') {
            v += oneBack;
        }
        //add two prior if they are between 10 and 26, less than 9 signifies two index before was 0
        //more than 26 means greater than Z and hence doesnt have a mapping
        int val = Integer.parseInt(s.substring(i-2, i));
        if (val > 9 && val < 27) {
            v += twoBack;
        }
        //move the counters forward
        twoBack = oneBack;
        oneBack = v;
    }
    return oneBack;
}