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).
Table of Contents
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];
}