Lookup table, DP O(n) runtime and O(1) space


  • 3
    T
    public class Solution {
        static final Map<String, Integer> map2 = new HashMap<>();
        static {
            map2.put("**", 15);
            map2.put("*0", 2);
            map2.put("*1", 2);
            map2.put("*2", 2);
            map2.put("*3", 2);
            map2.put("*4", 2);
            map2.put("*5", 2);
            map2.put("*6", 2);
            map2.put("1*", 9);
            map2.put("2*", 6);
            map2.put("27", 0);
            map2.put("28", 0);
            map2.put("29", 0);
        }
        static final Map<Character, Integer> map1 = new HashMap<>();
        static {
            map1.put('*', 9);
            map1.put('0', 0);
        }
        public int numDecodings(String s) {
            int n = s.length();
            s = s + "0";
            long cur = 0, pre1 = 1, pre2 = 0;
            for (int i = n - 1; i >= 0; i--) {
                char ch = s.charAt(i);
                
                cur = map1.getOrDefault(ch, 1) * pre1;
                if (ch == '*' || ch == '1' || ch == '2') {
                    cur += map2.getOrDefault(s.substring(i, i+2), 1) * pre2;
                }
                cur %= 1000000007;
                pre2 = pre1;
                pre1 = cur;
            }
    
            return (int) cur;
        }
    }
    

    Or, even shorter:

    public class Solution {
        static final int[][] map = new int[58][58];
        static {
            Arrays.fill(map['*'], 1);
            map['*']['*'] = 15;
            map['*']['0'] = 2;
            map['*']['1'] = 2;
            map['*']['2'] = 2;
            map['*']['3'] = 2;
            map['*']['4'] = 2;
            map['*']['5'] = 2;
            map['*']['6'] = 2;
            Arrays.fill(map['1'], 1);
            map['1']['*'] = 9;
            Arrays.fill(map['2'], 1);
            map['2']['*'] = 6;
            map['2']['7'] = 0;
            map['2']['8'] = 0;
            map['2']['9'] = 0;
            Arrays.fill(map[0], 1);
            map[0]['*'] = 9;
            map[0]['0'] = 0;
        }
    
        public int numDecodings(String s) {
            long cur = 1, pre = 0;
            char ch = 0, ch1 = '0';
            for (int i = s.length() - 1; i >= 0; i--) {
                ch = s.charAt(i);
                cur = (map[ch][ch1] * pre + map[0][(ch1 = ch)] * (pre = cur)) % 1000000007;
            }
    
            return (int) cur;
        }
    }
    

  • -1

    @tyuan73 I basically had same idea, but in recursion + memorization. But the call stack is too long for memory if input s is huge...

        int numDecodings(string s) {
            if (s.empty()) return 0;
            memo = vector<int>(s.size(), -1);
            return ways(s);
        }
        
        long ways(string s, int i = 0) {
            if (i == s.size()) return 1;
            if (i > s.size()) return 0;
            if (memo[i] >= 0) return memo[i];
            if (s[i] == '0') return 0;
            
            long res = 0;
            if (s[i] == '*') { 
                res = (9*ways(s, i+1))%MOD;
                if (i+1 < s.size()) {
                    if (s[i+1] == '*') (res += 15L*ways(s, i+2)) %= MOD;
                    else if (s[i+1] - '6' > 0) (res += ways(s, i+2)) %= MOD;
                    else (res += 2L*ways(s, i+2)) %= MOD;
                }
            }
            else {
                res = ways(s, i+1);
                if (i+1 < s.size()) {
                    if (s[i] == '1') {
                        if (s[i+1] == '*') (res += 9L*ways(s, i+2)) %= MOD;
                        else (res += ways(s, i+2)) %= MOD;
                    }
                    else if (s[i] == '2') {
                        if (s[i+1] == '*') (res += 6L*ways(s, i+2)) %= MOD;
                        else if (s[i+1] - '7' < 0) (res += ways(s, i+2)) %= MOD;
                    }
                }            
            }
            return memo[i] = res;
            
        }
        
        const int MOD = 1000000007;
        vector<int> memo;
    

Log in to reply
 

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