Decode Ways - Secret MessageA 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
Code:
import java.util.*;
public class Hello {
public static int num(String s){
if(s==null||s.length()==0||s.charAt(0)=='0')
return 0;
if(s.length()==1)
return 1;
int[] dp=new int[s.length()];
dp[0]=1;
if(Integer.parseInt(s.substring(0,2))>26)
{
if(s.charAt(1)!='0')
dp[1]=1;
else
dp[1]=0;
}
else
{
if(s.charAt(1)!='0')
dp[1]=2;
else
dp[1]=1;
}
for(int i=2;i<s.length();i++)
{
if(s.charAt(i)!='0')
dp[i]+=dp[i-1];
int val=Integer.parseInt(s.substring(i-1,i+1));
if(val<=26&&val>=10)
dp[i]+=dp[i-2];
}
return dp[s.length()-1];
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String st=sc.next();
System.out.print(num(st));
}
}
No comments:
Post a Comment