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"))