Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Subscribe to see which companies asked this question

solution:

Memory can be reduced to O(1). Idea is the same. DP.

public class Solution {
    public static String word;
    public static HashMap<Integer,Integer> map;
    public int numDecodings(String s) {
        word = s;
        map = new HashMap<>(); 
        if(s==null ||s.length() == 0) return 0;
        return help(0);
    }

    public int help(int index){
        if(index == word.length()) return 1;
        if(word.charAt(index) == '0') return 0;
        if(index == word.length()-1) return 1;
        int op1 = 0, op2 = 0;
        if(map.get(index+1) == null) {
            op1= help(index+1);
            map.put(index+1,op1);
        }
        else{
            op1 = map.get(index+1);
        }

        if(map.get(index+2) == null) {
            op2= help(index+2);
            map.put(index+2,op2);
        }
        else{
            op2 = map.get(index+2);
        }

        if(word.charAt(index) == '1'){
            if(word.charAt(index+1) == '0') return op2;
            return op1 + op2;
        }
        else if(word.charAt(index) =='2'){
            if(word.charAt(index+1) == '0') return op2;
            if(word.charAt(index+1) - '0' < 7) return op1 + op2;
        }
        return op1;  
    }
}