0091 Decode Ways

Question

My Solution:

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        int[] dp = new int[len+1];
        dp[0] = 1;

        if(s.charAt(0) != '0'){
            dp[1] = 1;
        }

        for(int i = 2; i < len+1; i++){
            if(s.charAt(i-1) != '0'){
                dp[i] += dp[i-1];
            }
            int val = Integer.valueOf(s.substring(i-2, i));
            if(val >= 10 
                && val <= 26){
                    dp[i] += dp[i-2];
            }
        }

        return dp[len];
    }
}

My Solution2 recursive:

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s) : 1}
        def dfs(i):
            if i in dp: # 
                return dp[i]
            if s[i] == "0":
                return 0
            
            res = dfs(i + 1)
            if(i + 1 < len(s) and (s[i] == "1" 
            or s[i] == "2" and s[i+1] in "0123456")):
                res += dfs(i+2)
            dp[i] = res

            return res
        return dfs(0)

My Solution3 DP:

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s) : 1}
        for i in range(len(s) - 1, -1, -1):
            if s[i] == "0":
                dp[i] = 0
            else:
                dp[i] = dp[i+1]
            if(i + 1 < len(s) and (s[i] == "1" or
            s[i] == "2" and s[i+1] in "0123456")):
                dp[i] += dp[i+2]
        return dp[0]