Decode Ways Problem Solution

Decode Ways Problem: Given a string s containing only digits, return the number of ways to decode it.

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Decode Ways Problem Solution

Problem Solution In Python

class Solution:
    def numDecodings(self, s: str) -> int:
        dic = {str(i):0 for i in range(100)}
        for i in range(11,27):
            dic[str(i)] = 1 
        for i in range(1,10):
            dic[str(i)] = 1
            dic["0"+str(i)] = 0
            dic[str(i)+"0"] = 0
        dic["00"],dic["10"],dic["20"] = 0,1,1
        if len(s) == 1:
            return dic[s]
        dp = [0]*len(s)
        dp[0] = dic[s[0]]
        dp[1] = dic[s[:2]]+dic[s[0]]*dic[s[1]]
        for k in range(2,len(s)):
            dp[k] = dp[k-1]*dic[s[k]]+dp[k-2]*dic[s[k-1:k+1]]
        return dp[-1]

Problem Solution In Java

class Solution {
    public int numDecodings(String s) {
        int l = s.length();
        int[] dp = new int[l];
        if(s.charAt(l-1)=='0')
            dp[l-1]=0;
        else
            dp[l-1]=1;
        for(int i=l-2;i>=0;i--){
            int a=s.charAt(i)-'0';
            int b=s.charAt(i+1)-'0';
            if(a==0){
                dp[i]=0;
                continue;
            }
            if(a==0 || a>=3 && b==0){
                return 0;
            }else if(a>=3 || (a==2 && b>6)){
                dp[i]=dp[i+1];
            }else if(b==0){
                dp[i]=(i+2<l?dp[i+2]:1);  
            }else{
                dp[i]=dp[i+1]+(i+2<l?dp[i+2]:1);
            }
            
        }
        return dp[0];
    }
}

Problem Solution In C++

class Solution {
public:
    int numDecodings(string s) 
    {
        int count = 0;
        queue<int> q;
        q.push(0);
        int d = 0;
        while (!q.empty())
        {
            int d = 0;
            int i = q.front();
            q.pop();
            for (; i<s.length(); i++)
            {
                d *= 10;
                d += s[i] -'0';
                if (d > 0 &&  d < 27)
                {
                    if (i+1 == s.length())
                    {
                        count++;
                    }
                    else
                        q.push(i+1);
                }
                else
                    break;
            }
            
        }
        return count;
        
    }
};

Problem Solution In C

int numDecodings(char* s) {
	int len = strlen(s);
	int* map = (int*)calloc(len + 1, sizeof(int));
	map[len] = 1;
	int i = len - 1;
	while (i >= 0)
	{
		if (s[i] == '0') map[i] = 0;
		else if (i == len - 1) map[i] = 1;
		else if (s[i] == '1' || (s[i] == '2'&&s[i + 1] <= '6')) map[i] = map[i + 1] + map[i + 2];
		else  map[i] = map[i + 1];
		i--;
	}
	return map[0];
}