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)
{
/*
---------------------------------------
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
*/
/*
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
*/
}
}``````

#### 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()
{
/*
---------------------------------------
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
*/
/*
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
*/
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)
{
/*
---------------------------------------
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
*/
/*
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
*/
}
}``````

#### 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()
{
/*
---------------------------------------
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
*/
/*
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
*/
}
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()
{
/*
---------------------------------------
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
*/
/*
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
*/
}
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() :
#    ---------------------------------------
#    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
#    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

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()
#    ---------------------------------------
#    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
#    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
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
*/
/*
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
*/
}
}``````

#### 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()
{
/*
---------------------------------------
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
*/
/*
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
*/
}
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
{
/*
---------------------------------------
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
*/
/*
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
*/
}``````

#### 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.

Categories
Relative Post