My accepted solution (Java) [275ms]


  • 0
    S
    public class Solution {
        //leetcode decode ways
        public int numDecodings(String s) {
            if(s.equals("") || s==null || s.length()==0) {
                return 0;
            }
            HashMap<String, String> map=new HashMap<String, String>();
            HashMap<String, Integer> cache=new HashMap<String, Integer>();
            for(char c='A'; c<='Z'; c++) {
                map.put(""+(c-'A'+1), ""+c);
            }
            return numDecodings(s, map, cache);
        }
        
        private int numDecodings(String s, HashMap<String, String> map, HashMap<String, Integer> cache) {
            if(s.length()==0) return 1;
            int result=0;
            if(cache.containsKey(s)) {
                return cache.get(s);
            }
            if(s.length()>1) {
                if( map.containsKey(s.substring(0, 1)) && map.containsKey(s.substring(0, 2))) {
                    result=numDecodings(s.substring(1), map, cache)+numDecodings(s.substring(2), map, cache);
                } else if( map.containsKey(s.substring(0, 1)) ) {
                    result=numDecodings(s.substring(1), map, cache);
                } else if( map.containsKey(s.substring(0, 2)) ) {
                    result=numDecodings(s.substring(2), map, cache);
                }
            } else if(map.containsKey(s)){
                result=1;
            }
            cache.put(s, result);
            return result;
        }
    }

  • 0
    L

    actually, you dont need the map, just need a cache, just calculate the 1 <= substr(1) <= 26, and 10 <= substr(2) <= 26


Log in to reply
 

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