Decode Ways

NeetCode: Decode Ways · LeetCode: 91. Decode Ways · Difficulty: Medium

A message of letters is encoded as digits with A -> 1, B -> 2, ..., Z -> 26. Given a digit string s, return the number of ways to decode it. A leading zero cannot be decoded ("06" is invalid), but 10 and 20 are valid codes.

Example

Text

Input:  s = "12"     Output: 2    ("AB" as 1,2 or "L" as 12)
Input:  s = "226"    Output: 3    (2,2,6 / 22,6 / 2,26)
Input:  s = "06"     Output: 0

At position i you can decode one digit (if it isn't '0') and continue at i + 1, or decode two digits (if they form 10 to 26) and continue at i + 2. Reaching the end of the string counts as one complete decoding.

Only the final answer is guaranteed to fit in an int. Java int addition wraps silently on overflow, so intermediate counts stay correct modulo 2^32 and the final result is exact.

Subtracting '0' from a char gives an int: s.charAt(i) - '0' is the digit value, because char operands are promoted to int in arithmetic.

Brute force: recursion

Java

class Solution {
    private int ways(String s, int i) {
        if (i == s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        int total = ways(s, i + 1);
        if (i + 1 < s.length()) {
            int two = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            if (two <= 26) {
                total += ways(s, i + 2);
            }
        }
        return total;
    }

    public int numDecodings(String s) {
        return ways(s, 0);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numDecodings("12"));
        System.out.println(solution.numDecodings("226"));
        System.out.println(solution.numDecodings("06"));
        System.out.println(solution.numDecodings("10"));
    }
}

Output

Each position has two branches and the subproblems overlap, as in Fibonacci. Time: O(2^n). Space: O(n) stack.

Better: memoization

ways(i) depends only on i, so its result can be cached in an Integer[], where null marks an empty slot.

Java

class Solution {
    private int ways(String s, int i, Integer[] memo) {
        if (i == s.length()) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        if (memo[i] != null) {
            return memo[i];
        }
        int total = ways(s, i + 1, memo);
        if (i + 1 < s.length()) {
            int two = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
            if (two <= 26) {
                total += ways(s, i + 2, memo);
            }
        }
        memo[i] = total;
        return total;
    }

    public int numDecodings(String s) {
        Integer[] memo = new Integer[s.length()]; // null means "not computed yet"
        return ways(s, 0, memo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numDecodings("12"));
        System.out.println(solution.numDecodings("226"));
        System.out.println(solution.numDecodings("06"));
        System.out.println(solution.numDecodings("10"));
    }
}

Output

Time: O(n). Space: O(n).

Optimal: bottom-up with two variables

Fill from the end of the string backwards. next1 holds ways(i + 1) and next2 holds ways(i + 2). A '0' at position i kills every decoding starting there; otherwise ways(i) = ways(i+1), plus ways(i+2) when the two digits form a number up to 26.

Java

class Solution {
    public int numDecodings(String s) {
        int next1 = 1; // ways(n)
        int next2 = 0; // ways(n + 1)
        for (int i = s.length() - 1; i >= 0; i--) {
            int cur;
            if (s.charAt(i) == '0') {
                cur = 0;
            } else {
                cur = next1;
                if (i + 1 < s.length() && (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26) {
                    cur += next2;
                }
            }
            next2 = next1;
            next1 = cur;
        }
        return next1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.numDecodings("12"));
        System.out.println(solution.numDecodings("226"));
        System.out.println(solution.numDecodings("06"));
        System.out.println(solution.numDecodings("10"));
    }
}

Output

Time: O(n). Space: O(1).

For "226": ways(3) = 1, ways(2) = 1 (only "6"), ways(1) = 1 + 1 = 2 ("2,6" or "26"), ways(0) = 2 + 1 = 3.