Problem Statement
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Sample Test Cases
Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Problem Solution
We will be using Dynamic Programming to solve this problem.
Let’s think of the sub problem. To decode a message of n characters, you need to know in how many ways you can decode message using n-1 characters and a message using n-2 characters.
Why are we going only two steps back ie n-1 and n-2 if we are calculating for n? Because the letter can be either represented by one character or a two characters.
So on each step keeping in mind the constraint that coding of letter is constrained between 1 and 26 we cascade through the array summing the values at n-1 and n-2.
Complexity Analysis
Time Complexity: O(n) as we are traversing through the entire array once.
Space Complexity: O(n) we have to maintain the dp array which has same size as string.
Code Implementation
#include<bits/stdc++.h>
using namespace std;
int numDecodings(string s) {
vector<int>dp(s.size()+1,0);
dp[0]=1;dp[1]=1;
if(s[0]=='0')return 0;
for(int i=2;i<=s.size();i++){
if(s[i-1]>'0')dp[i]=dp[i-1];
if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<'7'))dp[i]+=dp[i-2];
}
return dp[s.size()];
}
int main()
{
string s="226";
int x= numDecodings(s);
cout<<x;
}
public class Decode
{
public int numDecodings(String s)
{
if (s == null || s.length() == 0)
return 0;
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for (int i = 2; i <= n; i++)
{
int first = Integer.valueOf(s.substring(i - 1, i));
int second = Integer.valueOf(s.substring(i - 2, i));
if (first >= 1 && first <= 9)
dp[i] += dp[i-1];
if (second >= 10 && second <= 26)
dp[i] += dp[i-2];
}
return dp[n];
}
public static void main(String[] args)
{
Decode d = new Decode();
String s = "226";
System.out.println(d.numDecodings(s));
}
}
def numDecodings(s):
if not s or s[0] == '0':
return 0
prev, curr = 1, 1
for i in range(1,len(s)):
if s[i] == '0':
curr = 0
if s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6'):
tmp = curr
curr += prev
prev = tmp
else:
prev = curr
return curr
print(numDecodings("226"))
