A top secret message string S containing letters from A-Z (only upper case letters) is encoded to numbers using the following mapping:
‘A’ -> 1, ‘B’ -> 2 and so on till Z -> ’26’
The program has to print the total number of ways in which the received message can be decoded.
Input Format:
The first line contains the string S containing numbers.
Output Format:
The first line contains the number of ways in which S can be decoded.
Boundary Conditions:
1 <= Length of S <= 100
Example Input/Output 1:
Input:
123
Output:
3
Explanation:
1-A 2-B 3-C 12-L 23-W.
Hence 123 can be decoded as ABC or AW or LC, that is in 3 ways.
Example Input/Output 2:
Input:
1290
Output:
0
def decode(s): n=len(s) dp=[0 for i in range(n)] if s[0]!='0': dp[0]=1 for i in range(1,n): x=int(s[i]) y=int(s[i-1:i+1]) if x>=1 and x<=9: dp[i]+=dp[i-1] if y>=10 and y<=26: if i-1>0: dp[i]+=dp[i-2] else: dp[i]+=1 return dp[-1] n=(input()) print(decode(n))
import java.util.*; public class Main { public static void main(String[] args) { //Your Code Here Scanner scan=new Scanner(System.in); char str[]=scan.next().toCharArray(); int ways=1,prevWays=1; int l=str.length; if(str[l-1]=='0'){ ways=0; } for(int i=l-2;i>-1;--i){ int backUp=prevWays; prevWays=ways; if(str[i]=='0'){ ways=0; continue; } int twoDigi=Integer.parseInt(str[i]+""+str[i+1]); if(twoDigi<=26){ ways=ways+backUp; } } System.out.print(ways); } }
Leave a Reply