91. Decode Ways

三刷 06/2022

Version #1 DP - 1D array

Can be optimized to constant space

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 98.23% of Java online submissions for Decode Ways.

Memory Usage: 42.6 MB, less than 29.83% of Java online submissions for Decode Ways.

class Solution {

    public int numDecodings(String s) {

        int[] dp = new int[s.length() + 1];

        dp[0] = 1;

        if (s.length() == 0 || s.charAt(0) == '0') {

            return 0;

        }

        dp[1] = 1;

        for (int i = 2; i <= s.length(); i++) {

            int prev = s.charAt(i - 2) - '0';

            int curr = s.charAt(i - 1) - '0';

            if (curr != 0) {

                dp[i] += dp[i - 1]; // single digit decode is possible

            }

            if (prev == 0 && curr == 0) {

                return 0;

            }

            int twoDigit = prev * 10 + curr;

            if (twoDigit >= 10 && twoDigit <= 26) {

                dp[i] += dp[i - 2];

            }

        }

        return dp[s.length()];

    }

}

二刷

90.97 %
class Solution {
    public int numDecodings(String s) {
        // dp[i] -> number of ways to decode s.substring[0, i]
        if (s == null || s.length() == 0) return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            int curr = s.charAt(i - 1) - '0';
            if (i == 1) { // first position
                if (curr == 0) return 0;
                dp[i] = 1;
            } else {
                // decode by itself
                // decode with its previous digit
                int prev = s.charAt(i - 2) - '0';
                if (prev != 0 && prev * 10 + curr <= 26) {
                    dp[i] += dp[i - 2];
                }
                if (curr != 0) {
                    dp[i] += dp[i - 1];
                }
            }
        }
        return dp[s.length()];
    }
}

一刷
Space can be optimized

96.96 %
class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // dp[i] -> ways to decode substring [0, i)
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        int prev = 0;
        for (int i = 1; i <= s.length(); i++) {
            int curr = s.charAt(i - 1) - '0';
            int num = prev * 10 + curr;
            if (i > 1 && num >= 10 && num < 27) {
                dp[i] += dp[i - 2];
            }
            if (curr > 0) {
                dp[i] += dp[i - 1];
            }
            prev = curr;
        }
        return dp[s.length()];
    }
}