Posted on by Kalkicode
Code Dynamic Programming

Possible decodings of given digits using dynamic programming

In this article, we will explore the concept of decoding a sequence of digits using dynamic programming. The goal is to count the number of possible decodings for a given sequence of digits. We'll provide a detailed explanation of the problem, present a pseudocode algorithm, and analyze the time complexity of the solution. Additionally, we'll showcase the expected output for a couple of sample inputs.

Problem Statement

Given a sequence of digits, we want to determine the number of possible decodings. Each digit can be decoded as a corresponding letter from the alphabet, where '1' maps to 'A', '2' maps to 'B', and so on, until '26' maps to 'Z'.

Pseudocode Algorithm with Explanation

function countDecodes(digits)
    count = 0
    n = length of digits
    dp = array of size (n + 1)
	// Initialize dp array with zeros
	for i = 0 to n
		dp[i] = 0

	// Handle the last digit separately
	if last character of digits is not '0'
		dp[n - 1] = 1

	// Set the value of the last element of dp to 1
	dp[n] = 1

	// Traverse the digits from right to left
	for i = n - 2 to 0 with step -1
		if digits[i] is not '0'
			dp[i] = dp[i] + dp[i + 1]

		if digits[i] is '1'
			dp[i] = dp[i] + dp[i + 2]

		else if digits[i] is '2'
			if digits[i + 1] is less than or equal to '6'
				dp[i] = dp[i] + dp[i + 2]

	return dp[0]

The above pseudocode represents a dynamic programming approach to solve the problem. We maintain an array, dp, where dp[i] represents the number of possible decodings for the subsequence of digits starting at index i. We initialize dp[n - 1] to 1 because the last digit can always be decoded as a single character. Then, we iterate from the second-to-last digit to the first digit, updating dp[i] based on the digit and its neighboring digits. Finally, we return the value of dp[0], which represents the total number of possible decodings for the entire sequence of digits.

Code Solution

/*
    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

Resultant Output Explanation by Statement

We will now demonstrate the usage of the countDecodes function with two sample inputs: "78612" and "12821".

  1. For the input "78612":
  2. Given Digit: 78612
    Result: 2
    

    In this case, there are two possible decodings for the sequence of digits "78612". The first possible decoding is "G H F A B", and the second possible decoding is "G H F K".

  3. For the input "12821":
  4. Given Digit: 12821
    Result: 4
    

    In this case, there are four possible decodings for the sequence of digits "12821". The possible decodings are "A B H B A", "K B H B", "A B H U", and "K H U".

Time Complexity of the Code

The time complexity of the provided solution is O(n), where n is the length of the input digit sequence. This is because we iterate through the digits once to fill the dp array. The space complexity is also O(n) because we use an additional array of the same length to store the dynamic programming values.

By utilizing the dynamic programming approach, we can efficiently calculate the number of possible decodings for a given sequence of digits.

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