Skip to main content

Possible decodings of given digits using dynamic programming

Here given code implementation process.

/*
    Java Program for
    Possible decodings of given digits using dynamic programming
*/
public class Decodings
{
	public void countDecodes(String digits)
	{
		int count = 0;
		int n = digits.length();
		int[] dp = new int[n + 1];
		for (int i = 0; i <= n; ++i)
		{
			dp[i] = 0;
		}
		if (digits.charAt(n - 1) != '0')
		{
			// When last character of digit sequence is not zero
			dp[n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		dp[n] = 1;
		// Execute loop from n-2 to 0
		for (int i = n - 2; i >= 0; --i)
		{
			if (digits.charAt(i) != '0')
			{
				dp[i] = dp[i] + dp[i + 1];
			}
			if (digits.charAt(i) == '1')
			{
				dp[i] = dp[i] + dp[i + 2];
			}
			else if (digits.charAt(i) == '2')
			{
				if (digits.charAt(i + 1) <= '6')
				{
					dp[i] = dp[i] + dp[i + 2];
				}
			}
		}
		System.out.print("\n Given Digit  : " + digits);
		// Display calculated result
		System.out.println("\n Result  : " + dp[0]);
	}
	public static void main(String[] args)
	{
		Decodings task = new Decodings();
		/*
		    ---------------------------------------
		    1 : A  2 : B  3 : C  4 : D  5 : E
		    6 : F  7 : G  8 : H  9 : I  10 : J
		    11 : K  12 : L  13 : M  14 : N  15 : O
		    16 : P  17 : Q  18 : R  19 : S  20 : T
		    21 : U  22 : V  23 : W  24 : X  25 : Y
		    26 : Z
		    ---------------------------------------
		    Possible decode characters
		*/
		/*
		    digit = 7 8 6 1 2
		    ------------------
		            7 8 6 1 2
		            ☨ ☨ ☨ ☨ ☨  ➀
		            G H F A B
		    ------------------
		            7 8 6 12
		            ☨ ☨ ☨ ☨    ➁
		            G H F K
		    ------------------
		    Ans : 2
		*/
		task.countDecodes("78612");
		/*
		    digit = 1 2 8 2 1
		    ------------------
		            1 2 8 2 1
		            ☨ ☨ ☨ ☨ ☨  ➀
		            A B H B A
		    ------------------
		            12 8 2 1
		            ☨  ☨ ☨ ☨   ➁ 
		            K  B H B 
		    ------------------
		            1 2 8 21
		            ☨ ☨ ☨ ☨    ➂
		            A B H U 
		    ------------------
		            12  8  21
		            ☨   ☨  ☨   ➃
		            K   H  U
		    ------------------
		    Ans : 4
		*/
		task.countDecodes("12821");
	}
}

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
// Include header file
#include <iostream>

#include <string>

using namespace std;
/*
    C++ Program for
    Possible decodings of given digits using dynamic programming
*/
class Decodings
{
	public: void countDecodes(string digits)
	{
		int count = 0;
		int n = digits.length();
		int dp[n + 1];
		for (int i = 0; i <= n; ++i)
		{
			dp[i] = 0;
		}
		if (digits[n - 1] != '0')
		{
			// When last character of digit sequence is not zero
			dp[n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		dp[n] = 1;
		// Execute loop from n-2 to 0
		for (int i = n - 2; i >= 0; --i)
		{
			if (digits[i] != '0')
			{
				dp[i] = dp[i] + dp[i + 1];
			}
			if (digits[i] == '1')
			{
				dp[i] = dp[i] + dp[i + 2];
			}
			else if (digits[i] == '2')
			{
				if (digits[i + 1] <= '6')
				{
					dp[i] = dp[i] + dp[i + 2];
				}
			}
		}
		cout << "\n Given Digit  : " << digits;
		// Display calculated result
		cout << "\n Result  : " << dp[0] << endl;
	}
};
int main()
{
	Decodings *task = new Decodings();
	/*
	    ---------------------------------------
	    1 : A  2 : B  3 : C  4 : D  5 : E
	    6 : F  7 : G  8 : H  9 : I  10 : J
	    11 : K  12 : L  13 : M  14 : N  15 : O
	    16 : P  17 : Q  18 : R  19 : S  20 : T
	    21 : U  22 : V  23 : W  24 : X  25 : Y
	    26 : Z
	    ---------------------------------------
	    Possible decode characters
	*/
	/*
	    digit = 7 8 6 1 2
	    ------------------
	            7 8 6 1 2
	            ☨ ☨ ☨ ☨ ☨  ➀
	            G H F A B
	    ------------------
	            7 8 6 12
	            ☨ ☨ ☨ ☨    ➁
	            G H F K
	    ------------------
	    Ans : 2
	*/
	task->countDecodes("78612");
	/*
	    digit = 1 2 8 2 1
	    ------------------
	            1 2 8 2 1
	            ☨ ☨ ☨ ☨ ☨  ➀
	            A B H B A
	    ------------------
	            12 8 2 1
	            ☨  ☨ ☨ ☨   ➁ 
	            K  B H B 
	    ------------------
	            1 2 8 21
	            ☨ ☨ ☨ ☨    ➂
	            A B H U 
	    ------------------
	            12  8  21
	            ☨   ☨  ☨   ➃
	            K   H  U
	    ------------------
	    Ans : 4
	*/
	task->countDecodes("12821");
	return 0;
}

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
// Include namespace system
using System;
/*
    Csharp Program for
    Possible decodings of given digits using dynamic programming
*/
public class Decodings
{
	public void countDecodes(String digits)
	{
		int n = digits.Length;
		int[] dp = new int[n + 1];
		for (int i = 0; i <= n; ++i)
		{
			dp[i] = 0;
		}
		if (digits[n - 1] != '0')
		{
			// When last character of digit sequence is not zero
			dp[n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		dp[n] = 1;
		// Execute loop from n-2 to 0
		for (int i = n - 2; i >= 0; --i)
		{
			if (digits[i] != '0')
			{
				dp[i] = dp[i] + dp[i + 1];
			}
			if (digits[i] == '1')
			{
				dp[i] = dp[i] + dp[i + 2];
			}
			else if (digits[i] == '2')
			{
				if (digits[i + 1] <= '6')
				{
					dp[i] = dp[i] + dp[i + 2];
				}
			}
		}
		Console.Write("\n Given Digit  : " + digits);
		// Display calculated result
		Console.WriteLine("\n Result  : " + dp[0]);
	}
	public static void Main(String[] args)
	{
		Decodings task = new Decodings();
		/*
		    ---------------------------------------
		    1 : A  2 : B  3 : C  4 : D  5 : E
		    6 : F  7 : G  8 : H  9 : I  10 : J
		    11 : K  12 : L  13 : M  14 : N  15 : O
		    16 : P  17 : Q  18 : R  19 : S  20 : T
		    21 : U  22 : V  23 : W  24 : X  25 : Y
		    26 : Z
		    ---------------------------------------
		    Possible decode characters
		*/
		/*
		    digit = 7 8 6 1 2
		    ------------------
		            7 8 6 1 2
		            ☨ ☨ ☨ ☨ ☨  ➀
		            G H F A B
		    ------------------
		            7 8 6 12
		            ☨ ☨ ☨ ☨    ➁
		            G H F K
		    ------------------
		    Ans : 2
		*/
		task.countDecodes("78612");
		/*
		    digit = 1 2 8 2 1
		    ------------------
		            1 2 8 2 1
		            ☨ ☨ ☨ ☨ ☨  ➀
		            A B H B A
		    ------------------
		            12 8 2 1
		            ☨  ☨ ☨ ☨   ➁ 
		            K  B H B 
		    ------------------
		            1 2 8 21
		            ☨ ☨ ☨ ☨    ➂
		            A B H U 
		    ------------------
		            12  8  21
		            ☨   ☨  ☨   ➃
		            K   H  U
		    ------------------
		    Ans : 4
		*/
		task.countDecodes("12821");
	}
}

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
package main
import "fmt"
/*
    Go Program for
    Possible decodings of given digits using dynamic programming
*/

func countDecodes(digits string) {
	var n int = len(digits)
	var dp = make([] int, n + 1)
	if digits[n - 1] != '0' {
		// When last character of digit sequence is not zero
		dp[n - 1] = 1
	}
	// Set the value of last element of dp is 1
	dp[n] = 1
	// Execute loop from n-2 to 0
	for i := n - 2 ; i >= 0 ; i-- {
		if digits[i] != '0' {
			dp[i] = dp[i] + dp[i + 1]
		}
		if digits[i] == '1' {
			dp[i] = dp[i] + dp[i + 2]
		} else if digits[i] == '2' {
			if digits[i + 1] <= '6' {
				dp[i] = dp[i] + dp[i + 2]
			}
		}
	}
	fmt.Print("\n Given Digit  : ", digits)
	// Display calculated result
	fmt.Println("\n Result  : ", dp[0])
}
func main() {

	/*
	    ---------------------------------------
	    1 : A  2 : B  3 : C  4 : D  5 : E
	    6 : F  7 : G  8 : H  9 : I  10 : J
	    11 : K  12 : L  13 : M  14 : N  15 : O
	    16 : P  17 : Q  18 : R  19 : S  20 : T
	    21 : U  22 : V  23 : W  24 : X  25 : Y
	    26 : Z
	    ---------------------------------------
	    Possible decode characters
	*/
	/*
	    digit = 7 8 6 1 2
	    ------------------
	            7 8 6 1 2
	            ☨ ☨ ☨ ☨ ☨  ➀
	            G H F A B
	    ------------------
	            7 8 6 12
	            ☨ ☨ ☨ ☨    ➁
	            G H F K
	    ------------------
	    Ans : 2
	*/
	countDecodes("78612")
	/*
	    digit = 1 2 8 2 1
	    ------------------
	            1 2 8 2 1
	            ☨ ☨ ☨ ☨ ☨  ➀
	            A B H B A
	    ------------------
	            12 8 2 1
	            ☨  ☨ ☨ ☨   ➁ 
	            K  B H B 
	    ------------------
	            1 2 8 21
	            ☨ ☨ ☨ ☨    ➂
	            A B H U 
	    ------------------
	            12  8  21
	            ☨   ☨  ☨   ➃
	            K   H  U
	    ------------------
	    Ans : 4
	*/
	countDecodes("12821")
}

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
<?php
/*
    Php Program for
    Possible decodings of given digits using dynamic programming
*/
class Decodings
{
	public	function countDecodes($digits)
	{
		$n = strlen($digits);
		$dp = array_fill(0, $n + 1, 0);
		if ($digits[$n - 1] != '0')
		{
			// When last character of digit sequence is not zero
			$dp[$n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		$dp[$n] = 1;
		// Execute loop from n-2 to 0
		for ($i = $n - 2; $i >= 0; --$i)
		{
			if ($digits[$i] != '0')
			{
				$dp[$i] = $dp[$i] + $dp[$i + 1];
			}
			if ($digits[$i] == '1')
			{
				$dp[$i] = $dp[$i] + $dp[$i + 2];
			}
			else if ($digits[$i] == '2')
			{
				if ($digits[$i + 1] <= '6')
				{
					$dp[$i] = $dp[$i] + $dp[$i + 2];
				}
			}
		}
		echo("\n Given Digit  : ".$digits);
		// Display calculated result
		echo("\n Result  : ".$dp[0].
			"\n");
	}
}

function main()
{
	$task = new Decodings();
	/*
	    ---------------------------------------
	    1 : A  2 : B  3 : C  4 : D  5 : E
	    6 : F  7 : G  8 : H  9 : I  10 : J
	    11 : K  12 : L  13 : M  14 : N  15 : O
	    16 : P  17 : Q  18 : R  19 : S  20 : T
	    21 : U  22 : V  23 : W  24 : X  25 : Y
	    26 : Z
	    ---------------------------------------
	    Possible decode characters
	*/
	/*
	    digit = 7 8 6 1 2
	    ------------------
	            7 8 6 1 2
	            ☨ ☨ ☨ ☨ ☨  ➀
	            G H F A B
	    ------------------
	            7 8 6 12
	            ☨ ☨ ☨ ☨    ➁
	            G H F K
	    ------------------
	    Ans : 2
	*/
	$task->countDecodes("78612");
	/*
	    digit = 1 2 8 2 1
	    ------------------
	            1 2 8 2 1
	            ☨ ☨ ☨ ☨ ☨  ➀
	            A B H B A
	    ------------------
	            12 8 2 1
	            ☨  ☨ ☨ ☨   ➁ 
	            K  B H B 
	    ------------------
	            1 2 8 21
	            ☨ ☨ ☨ ☨    ➂
	            A B H U 
	    ------------------
	            12  8  21
	            ☨   ☨  ☨   ➃
	            K   H  U
	    ------------------
	    Ans : 4
	*/
	$task->countDecodes("12821");
}
main();

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
/*
    Node JS Program for
    Possible decodings of given digits using dynamic programming
*/
class Decodings
{
	countDecodes(digits)
	{
		var n = digits.length;
		var dp = Array(n + 1).fill(0);
		if (digits.charAt(n - 1) != '0')
		{
			// When last character of digit sequence is not zero
			dp[n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		dp[n] = 1;
		// Execute loop from n-2 to 0
		for (var i = n - 2; i >= 0; --i)
		{
			if (digits.charAt(i) != '0')
			{
				dp[i] = dp[i] + dp[i + 1];
			}
			if (digits.charAt(i) == '1')
			{
				dp[i] = dp[i] + dp[i + 2];
			}
			else if (digits.charAt(i) == '2')
			{
				if (digits.charAt(i + 1) <= '6')
				{
					dp[i] = dp[i] + dp[i + 2];
				}
			}
		}
		process.stdout.write("\n Given Digit  : " + digits);
		// Display calculated result
		console.log("\n Result  : " + dp[0]);
	}
}

function main()
{
	var task = new Decodings();
	/*
	    ---------------------------------------
	    1 : A  2 : B  3 : C  4 : D  5 : E
	    6 : F  7 : G  8 : H  9 : I  10 : J
	    11 : K  12 : L  13 : M  14 : N  15 : O
	    16 : P  17 : Q  18 : R  19 : S  20 : T
	    21 : U  22 : V  23 : W  24 : X  25 : Y
	    26 : Z
	    ---------------------------------------
	    Possible decode characters
	*/
	/*
	    digit = 7 8 6 1 2
	    ------------------
	            7 8 6 1 2
	            ☨ ☨ ☨ ☨ ☨  ➀
	            G H F A B
	    ------------------
	            7 8 6 12
	            ☨ ☨ ☨ ☨    ➁
	            G H F K
	    ------------------
	    Ans : 2
	*/
	task.countDecodes("78612");
	/*
	    digit = 1 2 8 2 1
	    ------------------
	            1 2 8 2 1
	            ☨ ☨ ☨ ☨ ☨  ➀
	            A B H B A
	    ------------------
	            12 8 2 1
	            ☨  ☨ ☨ ☨   ➁ 
	            K  B H B 
	    ------------------
	            1 2 8 21
	            ☨ ☨ ☨ ☨    ➂
	            A B H U 
	    ------------------
	            12  8  21
	            ☨   ☨  ☨   ➃
	            K   H  U
	    ------------------
	    Ans : 4
	*/
	task.countDecodes("12821");
}
main();

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
#    Python 3 Program for
#    Possible decodings of given digits using dynamic programming
class Decodings :
	def countDecodes(self, digits) :
		n = len(digits)
		dp = [0] * (n + 1)
		if (digits[n - 1] != '0') :
			#  When last character of digit sequence is not zero
			dp[n - 1] = 1
		
		#  Set the value of last element of dp is 1
		dp[n] = 1
		i = n - 2
		#  Execute loop from n-2 to 0
		while (i >= 0) :
			if (digits[i] != '0') :
				dp[i] = dp[i] + dp[i + 1]
			
			if (digits[i] == '1') :
				dp[i] = dp[i] + dp[i + 2]
			elif (digits[i] == '2') :
				if (digits[i + 1] <= '6') :
					dp[i] = dp[i] + dp[i + 2]
				
			
			i -= 1
		
		print("\n Given Digit  : ", digits, end = "")
		#  Display calculated result
		print("\n Result  : ", dp[0])
	

def main() :
	task = Decodings()
	#    ---------------------------------------
	#    1 : A  2 : B  3 : C  4 : D  5 : E
	#    6 : F  7 : G  8 : H  9 : I  10 : J
	#    11 : K  12 : L  13 : M  14 : N  15 : O
	#    16 : P  17 : Q  18 : R  19 : S  20 : T
	#    21 : U  22 : V  23 : W  24 : X  25 : Y
	#    26 : Z
	#    ---------------------------------------
	#    Possible decode characters
	#    digit = 7 8 6 1 2
	#    ------------------
	#            7 8 6 1 2
	#            ☨ ☨ ☨ ☨ ☨  ➀
	#            G H F A B
	#    ------------------
	#            7 8 6 12
	#            ☨ ☨ ☨ ☨    ➁
	#            G H F K
	#    ------------------
	#    Ans : 2
	task.countDecodes("78612")
	#    digit = 1 2 8 2 1
	#    ------------------
	#            1 2 8 2 1
	#            ☨ ☨ ☨ ☨ ☨  ➀
	#            A B H B A
	#    ------------------
	#            12 8 2 1
	#            ☨  ☨ ☨ ☨   ➁ 
	#            K  B H B 
	#    ------------------
	#            1 2 8 21
	#            ☨ ☨ ☨ ☨    ➂
	#            A B H U 
	#    ------------------
	#            12  8  21
	#            ☨   ☨  ☨   ➃
	#            K   H  U
	#    ------------------
	#    Ans : 4
	task.countDecodes("12821")

if __name__ == "__main__": main()

Output

 Given Digit  :  78612
 Result  :  2

 Given Digit  :  12821
 Result  :  4
#    Ruby Program for
#    Possible decodings of given digits using dynamic programming
class Decodings 
	def countDecodes(digits) 
		n = digits.length
		dp = Array.new(n + 1) {0}
		if (digits[n - 1] != '0') 
			#  When last character of digit sequence is not zero
			dp[n - 1] = 1
		end

		#  Set the value of last element of dp is 1
		dp[n] = 1
		i = n - 2
		#  Execute loop from n-2 to 0
		while (i >= 0) 
			if (digits[i] != '0') 
				dp[i] = dp[i] + dp[i + 1]
			end

			if (digits[i] == '1') 
				dp[i] = dp[i] + dp[i + 2]
			elsif (digits[i] == '2') 
				if (digits[i + 1] <= '6') 
					dp[i] = dp[i] + dp[i + 2]
				end

			end

			i -= 1
		end

		print("\n Given Digit  : ", digits)
		#  Display calculated result
		print("\n Result  : ", dp[0], "\n")
	end

end

def main() 
	task = Decodings.new()
	#    ---------------------------------------
	#    1 : A  2 : B  3 : C  4 : D  5 : E
	#    6 : F  7 : G  8 : H  9 : I  10 : J
	#    11 : K  12 : L  13 : M  14 : N  15 : O
	#    16 : P  17 : Q  18 : R  19 : S  20 : T
	#    21 : U  22 : V  23 : W  24 : X  25 : Y
	#    26 : Z
	#    ---------------------------------------
	#    Possible decode characters
	#    digit = 7 8 6 1 2
	#    ------------------
	#            7 8 6 1 2
	#            ☨ ☨ ☨ ☨ ☨  ➀
	#            G H F A B
	#    ------------------
	#            7 8 6 12
	#            ☨ ☨ ☨ ☨    ➁
	#            G H F K
	#    ------------------
	#    Ans : 2
	task.countDecodes("78612")
	#    digit = 1 2 8 2 1
	#    ------------------
	#            1 2 8 2 1
	#            ☨ ☨ ☨ ☨ ☨  ➀
	#            A B H B A
	#    ------------------
	#            12 8 2 1
	#            ☨  ☨ ☨ ☨   ➁ 
	#            K  B H B 
	#    ------------------
	#            1 2 8 21
	#            ☨ ☨ ☨ ☨    ➂
	#            A B H U 
	#    ------------------
	#            12  8  21
	#            ☨   ☨  ☨   ➃
	#            K   H  U
	#    ------------------
	#    Ans : 4
	task.countDecodes("12821")
end

main()

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
/*
    Scala Program for
    Possible decodings of given digits using dynamic programming
*/
class Decodings()
{
	def countDecodes(digits: String): Unit = {
		var n: Int = digits.length();
		var dp: Array[Int] = Array.fill[Int](n + 1)(0);
		if (digits.charAt(n - 1) != '0')
		{
			// When last character of digit sequence is not zero
			dp(n - 1) = 1;
		}
		// Set the value of last element of dp is 1
		dp(n) = 1;
		var i: Int = n - 2;
		// Execute loop from n-2 to 0
		while (i >= 0)
		{
			if (digits.charAt(i) != '0')
			{
				dp(i) = dp(i) + dp(i + 1);
			}
			if (digits.charAt(i) == '1')
			{
				dp(i) = dp(i) + dp(i + 2);
			}
			else if (digits.charAt(i) == '2')
			{
				if (digits.charAt(i + 1) <= '6')
				{
					dp(i) = dp(i) + dp(i + 2);
				}
			}
			i -= 1;
		}
		print("\n Given Digit  : " + digits);
		// Display calculated result
		println("\n Result  : " + dp(0));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Decodings = new Decodings();
		/*
		    ---------------------------------------
		    1 : A  2 : B  3 : C  4 : D  5 : E
		    6 : F  7 : G  8 : H  9 : I  10 : J
		    11 : K  12 : L  13 : M  14 : N  15 : O
		    16 : P  17 : Q  18 : R  19 : S  20 : T
		    21 : U  22 : V  23 : W  24 : X  25 : Y
		    26 : Z
		    ---------------------------------------
		    Possible decode characters
		*/
		/*
		    digit = 7 8 6 1 2
		    ------------------
		            7 8 6 1 2
		            ☨ ☨ ☨ ☨ ☨  ➀
		            G H F A B
		    ------------------
		            7 8 6 12
		            ☨ ☨ ☨ ☨    ➁
		            G H F K
		    ------------------
		    Ans : 2
		*/
		task.countDecodes("78612");
		/*
		    digit = 1 2 8 2 1
		    ------------------
		            1 2 8 2 1
		            ☨ ☨ ☨ ☨ ☨  ➀
		            A B H B A
		    ------------------
		            12 8 2 1
		            ☨  ☨ ☨ ☨   ➁ 
		            K  B H B 
		    ------------------
		            1 2 8 21
		            ☨ ☨ ☨ ☨    ➂
		            A B H U 
		    ------------------
		            12  8  21
		            ☨   ☨  ☨   ➃
		            K   H  U
		    ------------------
		    Ans : 4
		*/
		task.countDecodes("12821");
	}
}

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4
import Foundation;
/*
    Swift 4 Program for
    Possible decodings of given digits using dynamic programming
*/
class Decodings
{
	func countDecodes(_ data: String)
	{
      	let digits = Array(data);
		let n: Int = digits.count;
		var dp: [Int] = Array(repeating: 0, count: n + 1);
		if (digits[n - 1]  != "0")
		{
			// When last character of digit sequence is not zero
			dp[n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		dp[n] = 1;
		var i: Int = n - 2;
		// Execute loop from n-2 to 0
		while (i >= 0)
		{
			if (digits[i]  != "0")
			{
				dp[i] = dp[i] + dp[i + 1];
			}
			if (digits[i] == "1")
			{
				dp[i] = dp[i] + dp[i + 2];
			}
			else if (digits[i] == "2")
			{
				if (digits[i + 1] <= "6")
				{
					dp[i] = dp[i] + dp[i + 2];
				}
			}
			i -= 1;
		}
		print("\n Given Digit  : ", data, terminator: "");
		// Display calculated result
		print("\n Result  : ", dp[0]);
	}
}
func main()
{
	let task: Decodings = Decodings();
	/*
	    ---------------------------------------
	    1 : A  2 : B  3 : C  4 : D  5 : E
	    6 : F  7 : G  8 : H  9 : I  10 : J
	    11 : K  12 : L  13 : M  14 : N  15 : O
	    16 : P  17 : Q  18 : R  19 : S  20 : T
	    21 : U  22 : V  23 : W  24 : X  25 : Y
	    26 : Z
	    ---------------------------------------
	    Possible decode characters
	*/
	/*
	    digit = 7 8 6 1 2
	    ------------------
	            7 8 6 1 2
	            ☨ ☨ ☨ ☨ ☨  ➀
	            G H F A B
	    ------------------
	            7 8 6 12
	            ☨ ☨ ☨ ☨    ➁
	            G H F K
	    ------------------
	    Ans : 2
	*/
	task.countDecodes("78612");
	/*
	    digit = 1 2 8 2 1
	    ------------------
	            1 2 8 2 1
	            ☨ ☨ ☨ ☨ ☨  ➀
	            A B H B A
	    ------------------
	            12 8 2 1
	            ☨  ☨ ☨ ☨   ➁ 
	            K  B H B 
	    ------------------
	            1 2 8 21
	            ☨ ☨ ☨ ☨    ➂
	            A B H U 
	    ------------------
	            12  8  21
	            ☨   ☨  ☨   ➃
	            K   H  U
	    ------------------
	    Ans : 4
	*/
	task.countDecodes("12821");
}
main();

Output

 Given Digit  :  78612
 Result  :  2

 Given Digit  :  12821
 Result  :  4
/*
    Kotlin Program for
    Possible decodings of given digits using dynamic programming
*/
class Decodings
{
	fun countDecodes(digits: String): Unit
	{
		val n: Int = digits.length;
		val dp: Array < Int > = Array(n + 1)
		{
			0
		};
		if (digits.get(n - 1) != '0')
		{
			// When last character of digit sequence is not zero
			dp[n - 1] = 1;
		}
		// Set the value of last element of dp is 1
		dp[n] = 1;
		var i: Int = n - 2;
		// Execute loop from n-2 to 0
		while (i >= 0)
		{
			if (digits.get(i) != '0')
			{
				dp[i] = dp[i] + dp[i + 1];
			}
			if (digits.get(i) == '1')
			{
				dp[i] = dp[i] + dp[i + 2];
			}
			else if (digits.get(i) == '2')
			{
				if (digits.get(i + 1) <= '6')
				{
					dp[i] = dp[i] + dp[i + 2];
				}
			}
			i -= 1;
		}
		print("\n Given Digit  : " + digits);
		// Display calculated result
		println("\n Result  : " + dp[0]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Decodings = Decodings();
	/*
	    ---------------------------------------
	    1 : A  2 : B  3 : C  4 : D  5 : E
	    6 : F  7 : G  8 : H  9 : I  10 : J
	    11 : K  12 : L  13 : M  14 : N  15 : O
	    16 : P  17 : Q  18 : R  19 : S  20 : T
	    21 : U  22 : V  23 : W  24 : X  25 : Y
	    26 : Z
	    ---------------------------------------
	    Possible decode characters
	*/
	/*
	    digit = 7 8 6 1 2
	    ------------------
	            7 8 6 1 2
	            ☨ ☨ ☨ ☨ ☨  ➀
	            G H F A B
	    ------------------
	            7 8 6 12
	            ☨ ☨ ☨ ☨    ➁
	            G H F K
	    ------------------
	    Ans : 2
	*/
	task.countDecodes("78612");
	/*
	    digit = 1 2 8 2 1
	    ------------------
	            1 2 8 2 1
	            ☨ ☨ ☨ ☨ ☨  ➀
	            A B H B A
	    ------------------
	            12 8 2 1
	            ☨  ☨ ☨ ☨   ➁ 
	            K  B H B 
	    ------------------
	            1 2 8 21
	            ☨ ☨ ☨ ☨    ➂
	            A B H U 
	    ------------------
	            12  8  21
	            ☨   ☨  ☨   ➃
	            K   H  U
	    ------------------
	    Ans : 4
	*/
	task.countDecodes("12821");
}

Output

 Given Digit  : 78612
 Result  : 2

 Given Digit  : 12821
 Result  : 4




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment