91. Decode Ways

class Solution {
    private Map<Integer, Integer> m = new HashMap<Integer, Integer>();
    public int numDecodings(String s) {
        return helper(0, s);
        
    }
    
    public int helper(int index, String s) {
        if (m.containsKey(index)) {
            return m.get(index);
        }
        
        if (index == s.length()) {
            return 1;
        }
        
        if (s.charAt(index) == '0') {
            return 0;
        }
        
        if (index == s.length() - 1) {
            return 1; 
        }
        
        int ans = helper(index + 1, s);
        
        if (Integer.parseInt(s.substring(index, index + 2)) <= 26) {
            ans += helper(index + 2, s);
        }
        
        m.put(index, ans);
        
        return ans; 
    }
}

Runtime: 3 ms, faster than 17.53% of Java online submissions for Decode Ways.
Memory Usage: 39.8 MB, less than 6.36% of Java online submissions for Decode Ways.

class Solution {

    public int numDecodings(String s) {
        // DP array to store the subproblem results
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        
        // Ways to decode a string of size 1 is 1. Unless the string is '0'.
        // '0' doesn't have a single digit decode.
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        for(int i = 2; i < dp.length; i++) {
            // Check if successful single digit decode is possible.
            if (s.charAt(i - 1) != '0') {
               dp[i] = dp[i - 1];  
            }
            
            // Check if successful two digit decode is possible.
            int twoDigit = Integer.valueOf(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[s.length()];
    }
}

Runtime: 2 ms, faster than 33.93% of Java online submissions for Decode Ways.
Memory Usage: 39 MB, less than 17.63% of Java online submissions for Decode Ways.

dp쓰는 루션이

class Solution {
    public int numDecodings(String s) {  
        if (s.charAt(0) == '0') {
            return 0;
        }

        int n = s.length();
        int twoBack = 1;
        int oneBack = 1;
        for (int i = 1; i < n; i++) {
            int current = 0;
            if (s.charAt(i) != '0') {
                current = oneBack;
            }
            int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1));
            if (twoDigit >= 10 && twoDigit <= 26) {
                current += twoBack;
            }
           
            twoBack = oneBack;
            oneBack = current;
        }
        return oneBack;
    }
}

Runtime: 4 ms, faster than 12.15% of Java online submissions for Decode Ways.
Memory Usage: 39.3 MB, less than 8.53% of Java online submissions for Decode Ways.

Constant space쓰는 방식