Dynamic Programming 07

A top secret message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 You are an FBI agent. You have to determine the total number of ways that message can be decoded.

Problem link :- click here

Code

import java.util.Scanner;

// TOTAL DECODING MESSAGES

public class DynamicProgramming_07
{
	
	static int totalDecodingMessages(String str)
	{
		if(str.length() == 0)
			return 1;
		if(str.charAt(0) == '0')
			return Integer.MIN_VALUE;
		if(str.substring(str.length()-2) == "00")
			return Integer.MIN_VALUE;
		
		return totalDecodingMessages2(str);
	}
	
	//recursion
	static int totalDecodingMessages1(String str)
	{
		int n = str.length();
		
		//Condition 5
		if(n == 0)
			return 1;
		
		int a = Integer.parseInt( str.substring(n-1) ) ;
		if(n == 1)
		{
			if(a >= 1)
				return 1;
			else
				return 0;
		}
		
		int b = Integer.parseInt( str.substring(n-2) );
		
		//Condition 4
		if(b==0)
			return Integer.MIN_VALUE;
		
		//Condition 3
		if(b>26 && a==0)
			return Integer.MIN_VALUE;
		
		if(n==2)
		{
			if(b>=10 && b<=26)
			{
				if(a>=1)
					return 2;
				else
					return 1;
			}
			else							//Condition 2
			{
				if(a >= 1)
					return 1;
				else
					return 0;
			}
		}
		
		
		int a_ans=0, b_ans=0;
		
		if(a >= 1)						//Condition 1
			a_ans = totalDecodingMessages1(str.substring(0, n-1));
		if(b>=10 && b <= 26)			//Condition 2
			b_ans = totalDecodingMessages1(str.substring(0, n-2));
		
		return a_ans + b_ans;
	}
	
	//DP
	static int totalDecodingMessages2(String str)
	{
		int n = str.length();
		int decode[] = new int[n];
		
		int a = Integer.parseInt( str.substring(n-1) );
		if(a >= 1)
			decode[n-1] = 1;
		else
			decode[n-1] = 0;
		
		int b = Integer.parseInt( str.substring(n-2) );
		if(b>26 && a==0)				//Condition 3
			return -1;
		else if(b>=10 && b<=26)
			decode[n-2] = decode[n-1] + 1;
		else
			decode[n-2] = decode[n-1];
		
		
		for(int i=n-3; i>=0; i--)
		{
			a = Integer.parseInt( str.substring(i+1, i+2) );
			b = Integer.parseInt( str.substring(i,     i+2) );
			
			if(b>26 && a==0)
				return -1;
			
			if(b>=10 && b<=26 && str.charAt(i+1) != '0' && str.charAt(i+2)!='0')
				decode[i] = decode[i+1] + 1;
			else
				decode[i] = decode[i+1];
		}
		
		for(int x:decode)
			System.out.print(x + "\t");
		return decode[0];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the string : ");
		String str = s.next();
		
		int ans = totalDecodingMessages(str);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}