Java DP solution using memoization


  • 0
    L
    class Solution {
        
         public int numDecodings(String s) {
             if (s.isEmpty()) {
                 return 0;
             }
             
             HashMap<String, Integer> cache = new HashMap<String, Integer>();
             
             return numDecodingsInternal(s, cache);
         }
        
        public int numDecodingsInternal(String s, Map<String, Integer> cache) {   
            if (cache.containsKey(s)) {
                return cache.get(s);
            }
            
            if (s.length() == 0) {
                return 1;
            }
            
            if (s.startsWith("0")) {
                return 0;
            }
            
            int result = 0;
            
            if (s.length() >= 2) {
                int parsed = Integer.parseInt(s.substring(0, 2));
                
                if (parsed >= 10 && parsed <= 26) {
                    result += numDecodingsInternal(s.substring(2, s.length()), cache);
                }
                
            }
            
            if (s.length() >= 1) {
                int parsed = Integer.parseInt(s.substring(0, 1));
                
                if (parsed >= 1 && parsed <= 9) {
                     result += numDecodingsInternal(s.substring(1, s.length()), cache);
                }
            }
            
            cache.put(s, result);
            
            return result;
        }
    }
    

Log in to reply
 

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