Java DP beat 100% O(n) time O(1) space


  • 0

    When we encounter a new character we can treat it as a individual encoding or combine with the previous character represent an encoding if possible. '' at the current bit can have maximum of 9 possibilities while '' at the previous bit can have maximum of 2 possibilities.

        public int numDecodings(String s) {
            if (s.charAt(0) == '0') return 0;
            long[] dp = new long[s.length()+1];
            int mod = 1000000007;
            dp[0] = 1;
            dp[1] = s.charAt(0) == '*' ? 9 : 1;
            for (int i = 2; i <= s.length(); i++) {
                char c = s.charAt(i-1);
                if (c == '0') {
                    if (s.charAt(i-2) != '1' && s.charAt(i-2) != '2' && s.charAt(i-2) != '*') return 0;
                    if (s.charAt(i-2) == '*') dp[i] = (2*dp[i-2]) % mod;
                    else dp[i] = dp[i-2];
                } else if (c != '*') {
                    dp[i] = dp[i-1];
                    if (s.charAt(i-2) == '1' || s.charAt(i-2) == '2' && c <= '6') dp[i] = (dp[i] + dp[i-2]) % mod;
                    else if (s.charAt(i-2) == '*') {
                        if (c <= '6') dp[i] = (dp[i] + 2*dp[i-2]) % mod;
                        else dp[i] = (dp[i] + dp[i-2]) % mod;
                    }
                } else {
                    dp[i] = (9*dp[i-1]) % mod;
                    if (s.charAt(i-2) == '1') dp[i] = (dp[i] + 9*dp[i-2]) % mod;
                    else if (s.charAt(i-2) == '2') dp[i] = (dp[i] + 6*dp[i-2]) % mod;
                    else if (s.charAt(i-2) == '*') dp[i] = (dp[i] + 15*dp[i-2]) % mod;
                }
            }
            return (int) dp[s.length()];
        }
    

    To reduce the space to O(1) we can replace dp[][] array with only two variables prev and cur

        public static int numDecodings(String s) {
            if (s.charAt(0) == '0') return 0;
            int mod = 1000000007;
            long prev = 1, cur = s.charAt(0) == '*' ? 9 : 1;
            for (int i = 2; i <= s.length(); i++) {
                long tmp = cur;
                char c = s.charAt(i-1);
                if (c == '0') {
                    if (s.charAt(i-2) != '1' && s.charAt(i-2) != '2' && s.charAt(i-2) != '*') return 0;
                    if (s.charAt(i-2) == '*') cur = (2*prev) % mod;
                    else cur = prev;
                } else if (c != '*') {
                    if (s.charAt(i-2) == '1' || s.charAt(i-2) == '2' && c <= '6') cur = (cur + prev) % mod;
                    else if (s.charAt(i-2) == '*') {
                        if (c <= '6') cur = (cur + 2*prev) % mod;
                        else cur = (cur + prev) % mod;
                    }
                } else {
                    if (s.charAt(i-2) == '1') cur = (9*cur + 9*prev) % mod;
                    else if (s.charAt(i-2) == '2') cur = (9*cur + 6*prev) % mod;
                    else if (s.charAt(i-2) == '*') cur = (9*cur + 15*prev) % mod;
                    else cur = 9*cur;
                }
                prev = tmp;
            }
            return (int) cur;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.