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 : 4package 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 : 4import 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 : 4Resultant Output Explanation by Statement
We will now demonstrate the usage of the countDecodes function with two sample inputs: "78612" and "12821".
- For the input "78612":
- For the input "12821":
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".
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.
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