Memoization, Java, 4ms.


  • 0
    N

    /**

    • use two arrays - useMap and dontUseMap.
    • useMap[i] = no. of ways of decoding from this point if you consider previous index entry
    • dontUseMap[i] = no. of ways of decoding from this point if you don't consider previous entry.

    **/

    public int numDecodings(String s) {
        if(s==null || s.length()==0) return 0;
        int [] useMap = new int[s.length()];
        int [] dontUseMap = new int[s.length()];
        Arrays.fill(useMap, -1);
        Arrays.fill(dontUseMap, -1);
        return decodingHelper(s, true, 0, useMap, dontUseMap);
        
    }
    
    private int decodingHelper(String s, boolean usePrevious, int index, int [] useMap, int [] dontUseMap ){
      
        if(s.length() == index){
            return 1;
        }
        
        int ways = 0;
        if(isValid(s.charAt(index) - '0')){
            if(useMap[index]!=-1){
                return useMap[index];
            }
            ways += decodingHelper(s, true, index+1, useMap, dontUseMap) ;
            useMap[index] =  ways;
        }
        
        if(index>0 && usePrevious){
            int temp = Integer.parseInt((s.substring(index-1, index+1)));
            if(isValid(temp)){
                if(dontUseMap[index]!=-1){
                    return dontUseMap[index];
                }
                ways += decodingHelper(s, false, index+1, useMap, dontUseMap);
                dontUseMap[index] =  ways;
            }
        }
        
        return ways;
    }
    
    
    private boolean isValid(int ret){
        if(ret>=1 && ret<=26) return true;
        return false;
    }
    

    }


Log in to reply
 

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