Problem:

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.

Method 1: by DP

Consider the current character and the previous character.

Code for method 1:

// dp
public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) return 0;
        if (s.charAt(0) == '0') return 0;
        // at least one elements here, and not 0;
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= s.length(); i++){
        
            if(s.charAt(i - 2) > '2' && s.charAt(i-1) == '0'){
                dp[i] = 0;
            }else if (s.charAt(i - 2) > '2' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '1' &&s.charAt(i-1) <= '6' ){
                dp[i] = dp[i-1]+dp[i-2];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) == '0'){
                dp[i] = dp[i-2];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '7' ){
                dp[i] = dp[i-1];
            }else if (s.charAt(i-2) == '1' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1]+dp[i-2];
            }else if (s.charAt(i-2) == '1' && s.charAt(i-1) == '0'){
                 dp[i] = dp[i-2];
            }else if (s.charAt(i-2) == '0' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1];
            }else{
                dp[i] = 0;
            }
        }
        return dp[s.length()];
    }
}

Another more beautiful code for method 1:

public int numDecodings(String s) {  
        if (s.length()==0||s==null||s=="0") 
            return 0; 

        int[] dp = new int[s.length()+1];  
        dp[0] = 1;  
        
        if (isValid(s.substring(0,1)))
            dp[1] = 1;  
        else 
            dp[1] = 0; 
        
        for(int i=2; i<=s.length();i++){  
            if (isValid(s.substring(i-1,i)))  
                dp[i] += dp[i-1];  
            if (isValid(s.substring(i-2,i)))  
                dp[i] += dp[i-2];  
        }  
        return dp[s.length()];  
    }  
      
    public boolean isValid(String s){  
        if (s.charAt(0)=='0') 
            return false;  
        int code = Integer.parseInt(s);  
        return code>=1 && code<=26;  
    }

Method 2: by Recursion. Too slow.

// by recursive
public class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        if (len == 0) return 0;
        if (len == 1 ){
            if (isValid(s.substring(0,1))) return 1;
            else return 0;
        }
        int res = 0;
        // at least have two elements here.
        if (isValid(s.substring(len-1,len))) res += numDecodings(s.substring(0,len-1));
        if (isValid(s.substring(len-2, len))) res += numDecodings(s.substring(0,len-2));

        return res;
    }
    
    public boolean isValid (String s){
        if (s.length() == 0 ) return false;
        int i = Integer.parseInt(s);
        if ( i >= 1 && i <= 26 ) return true;
        else return false;
    }
}