Distinct subsequences using dynamic programming
Here given code implementation process.
// C Program
// Distinct subsequences using dynamic programming
#include <stdio.h>
#include <string.h>
void distinctSubsequences(char *sequence, char *word)
{
// Get the length of sequence
int n = strlen(sequence);
// Get the length of word
int m = strlen(word);
int dp[n + 1][m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i][0] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
printf("\n Sequence : %s ", sequence);
printf("\n Word : %s", word);
// Display calculated result
printf("\n Result : %d", dp[n][m]);
}
int main()
{
char *sequence = "initcometipe";
char *word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
distinctSubsequences(sequence, word);
return 0;
}
Output
Sequence : initcometipe
Word : ice
Result : 4
// Java program for
// Distinct subsequences using dynamic programming
public class Subsequence
{
public void distinctSubsequences(String sequence, String word)
{
// Get the length of sequence
int n = sequence.length();
// Get the length of word
int m = word.length();
int[][] dp = new int[n + 1][m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i][0] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence.charAt(i) == word.charAt(j))
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
System.out.print("\n Sequence : " + sequence);
System.out.print("\n Word : " + word);
// Display calculated result
System.out.print("\n Result : " + dp[n][m]);
}
public static void main(String[] args)
{
Subsequence task = new Subsequence();
String sequence = "initcometipe";
String word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
}
Output
Sequence : initcometipe
Word : ice
Result : 4
// Include header file
#include <iostream>
#include <string>
using namespace std;
// C++ program for
// Distinct subsequences using dynamic programming
class Subsequence
{
public: void distinctSubsequences(string sequence, string word)
{
// Get the length of sequence
int n = sequence.length();
// Get the length of word
int m = word.length();
int dp[n + 1][m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i][0] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
cout << "\n Sequence : " << sequence;
cout << "\n Word : " << word;
// Display calculated result
cout << "\n Result : " << dp[n][m];
}
};
int main()
{
Subsequence *task = new Subsequence();
string sequence = "initcometipe";
string word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task->distinctSubsequences(sequence, word);
return 0;
}
Output
Sequence : initcometipe
Word : ice
Result : 4
// Include namespace system
using System;
// Csharp program for
// Distinct subsequences using dynamic programming
public class Subsequence
{
public void distinctSubsequences(String sequence, String word)
{
// Get the length of sequence
int n = sequence.Length;
// Get the length of word
int m = word.Length;
int[,] dp = new int[n + 1,m + 1];
// Set initial value of first column
for (int i = 0; i <= n; ++i)
{
dp[i,0] = 1;
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1,j + 1] = dp[i,j] + dp[i,j + 1];
}
else
{
dp[i + 1,j + 1] = dp[i,j + 1];
}
}
}
// Display given data
Console.Write("\n Sequence : " + sequence);
Console.Write("\n Word : " + word);
// Display calculated result
Console.Write("\n Result : " + dp[n,m]);
}
public static void Main(String[] args)
{
Subsequence task = new Subsequence();
String sequence = "initcometipe";
String word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
}
Output
Sequence : initcometipe
Word : ice
Result : 4
package main
import "fmt"
// Go program for
// Distinct subsequences using dynamic programming
func distinctSubsequences(sequence, word string) {
// Get the length of sequence
var n int = len(sequence)
// Get the length of word
var m int = len(word)
var dp = make([][] int, n + 1)
for i:= 0; i < n + 1;i++ {
dp[i] = make([]int,m+1)
}
// Set initial value of first column
for i := 0 ; i <= n ; i++ {
dp[i][0] = 1
}
for i := 0 ; i < n ; i++ {
for j := 0 ; j < m ; j++ {
if sequence[i] == word[j] {
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
} else {
dp[i + 1][j + 1] = dp[i][j + 1]
}
}
}
// Display given data
fmt.Print("\n Sequence : ", sequence)
fmt.Print("\n Word : ", word)
// Display calculated result
fmt.Print("\n Result : ", dp[n][m])
}
func main() {
var sequence string = "initcometipe"
var word string = "ice"
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
distinctSubsequences(sequence, word)
}
Output
Sequence : initcometipe
Word : ice
Result : 4
<?php
// Php program for
// Distinct subsequences using dynamic programming
class Subsequence
{
public function distinctSubsequences($sequence, $word)
{
// Get the length of sequence
$n = strlen($sequence);
// Get the length of word
$m = strlen($word);
$dp = array_fill(0, $n + 1, array_fill(0, $m + 1, 0));
// Set initial value of first column
for ($i = 0; $i <= $n; ++$i)
{
$dp[$i][0] = 1;
}
for ($i = 0; $i < $n; ++$i)
{
for ($j = 0; $j < $m; ++$j)
{
if ($sequence[$i] == $word[$j])
{
// Change value when sequence contains word element
$dp[$i + 1][$j + 1] = $dp[$i][$j] + $dp[$i][$j + 1];
}
else
{
$dp[$i + 1][$j + 1] = $dp[$i][$j + 1];
}
}
}
// Display given data
echo("\n Sequence : ".$sequence);
echo("\n Word : ".$word);
// Display calculated result
echo("\n Result : ".$dp[$n][$m]);
}
}
function main()
{
$task = new Subsequence();
$sequence = "initcometipe";
$word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
$task->distinctSubsequences($sequence, $word);
}
main();
Output
Sequence : initcometipe
Word : ice
Result : 4
// Node JS program for
// Distinct subsequences using dynamic programming
class Subsequence
{
distinctSubsequences(sequence, word)
{
// Get the length of sequence
var n = sequence.length;
// Get the length of word
var m = word.length;
var dp = Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
// Set initial value of first column
for (var i = 0; i <= n; ++i)
{
dp[i][0] = 1;
}
for (var i = 0; i < n; ++i)
{
for (var j = 0; j < m; ++j)
{
if (sequence.charAt(i) == word.charAt(j))
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
}
}
// Display given data
process.stdout.write("\n Sequence : " + sequence);
process.stdout.write("\n Word : " + word);
// Display calculated result
process.stdout.write("\n Result : " + dp[n][m]);
}
}
function main()
{
var task = new Subsequence();
var sequence = "initcometipe";
var word = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
main();
Output
Sequence : initcometipe
Word : ice
Result : 4
# Python 3 program for
# Distinct subsequences using dynamic programming
class Subsequence :
def distinctSubsequences(self, sequence, word) :
# Get the length of sequence
n = len(sequence)
# Get the length of word
m = len(word)
dp = [[0] * (m + 1) for _ in range(n + 1) ]
i = 0
# Set initial value of first column
while (i <= n) :
dp[i][0] = 1
i += 1
i = 0
while (i < n) :
j = 0
while (j < m) :
if (sequence[i] == word[j]) :
# Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
else :
dp[i + 1][j + 1] = dp[i][j + 1]
j += 1
i += 1
# Display given data
print("\n Sequence : ", sequence, end = "")
print("\n Word : ", word, end = "")
# Display calculated result
print("\n Result : ", dp[n][m], end = "")
def main() :
task = Subsequence()
sequence = "initcometipe"
word = "ice"
# sequence : initcometipe
# word : ice
# ------------------
# initcometipe
# - - - ➀ [ice]
# initcometipe
# - - - ➁ [ice]
# initcometipe
# - - - ➂ [ice]
# initcometipe
# - - - ➃ [ice]
# -------------------------------
# 4 possible sequence
task.distinctSubsequences(sequence, word)
if __name__ == "__main__": main()
Output
Sequence : initcometipe
Word : ice
Result : 4
# Ruby program for
# Distinct subsequences using dynamic programming
class Subsequence
def distinctSubsequences(sequence, word)
# Get the length of sequence
n = sequence.length
# Get the length of word
m = word.length
dp = Array.new(n + 1) {Array.new(m + 1) {0}}
i = 0
# Set initial value of first column
while (i <= n)
dp[i][0] = 1
i += 1
end
i = 0
while (i < n)
j = 0
while (j < m)
if (sequence[i] == word[j])
# Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
else
dp[i + 1][j + 1] = dp[i][j + 1]
end
j += 1
end
i += 1
end
# Display given data
print("\n Sequence : ", sequence)
print("\n Word : ", word)
# Display calculated result
print("\n Result : ", dp[n][m])
end
end
def main()
task = Subsequence.new()
sequence = "initcometipe"
word = "ice"
# sequence : initcometipe
# word : ice
# ------------------
# initcometipe
# - - - ➀ [ice]
# initcometipe
# - - - ➁ [ice]
# initcometipe
# - - - ➂ [ice]
# initcometipe
# - - - ➃ [ice]
# -------------------------------
# 4 possible sequence
task.distinctSubsequences(sequence, word)
end
main()
Output
Sequence : initcometipe
Word : ice
Result : 4
import scala.collection.mutable._;
// Scala program for
// Distinct subsequences using dynamic programming
class Subsequence()
{
def distinctSubsequences(sequence: String, word: String): Unit = {
// Get the length of sequence
var n: Int = sequence.length();
// Get the length of word
var m: Int = word.length();
var dp: Array[Array[Int]] = Array.fill[Int](n + 1, m + 1)(0);
var i: Int = 0;
// Set initial value of first column
while (i <= n)
{
dp(i)(0) = 1;
i += 1;
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (sequence.charAt(i) == word.charAt(j))
{
// Change value when sequence contains word element
dp(i + 1)(j + 1) = dp(i)(j) + dp(i)(j + 1);
}
else
{
dp(i + 1)(j + 1) = dp(i)(j + 1);
}
j += 1;
}
i += 1;
}
// Display given data
print("\n Sequence : " + sequence);
print("\n Word : " + word);
// Display calculated result
print("\n Result : " + dp(n)(m));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subsequence = new Subsequence();
var sequence: String = "initcometipe";
var word: String = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
}
Output
Sequence : initcometipe
Word : ice
Result : 4
import Foundation;
// Swift 4 program for
// Distinct subsequences using dynamic programming
class Subsequence
{
func distinctSubsequences(_ s: String, _ w: String)
{
let sequence = Array(s);
let word = Array(w);
// Get the length of sequence
let n: Int = sequence.count;
// Get the length of word
let m: Int = word.count;
var dp: [[Int]] =
Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1);
var i: Int = 0;
// Set initial value of first column
while (i <= n)
{
dp[i][0] = 1;
i += 1;
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (sequence[i] == word[j])
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
j += 1;
}
i += 1;
}
// Display given data
print("\n Sequence : ", s, terminator: "");
print("\n Word : ", w, terminator: "");
// Display calculated result
print("\n Result : ", dp[n][m], terminator: "");
}
}
func main()
{
let task: Subsequence = Subsequence();
let sequence: String = "initcometipe";
let word: String = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
main();
Output
Sequence : initcometipe
Word : ice
Result : 4
// Kotlin program for
// Distinct subsequences using dynamic programming
class Subsequence
{
fun distinctSubsequences(sequence: String, word: String): Unit
{
// Get the length of sequence
val n: Int = sequence.length;
// Get the length of word
val m: Int = word.length;
var dp: Array < Array < Int >> = Array(n + 1)
{
Array(m + 1)
{
0
}
};
var i: Int = 0;
// Set initial value of first column
while (i <= n)
{
dp[i][0] = 1;
i += 1;
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (sequence.get(i) == word.get(j))
{
// Change value when sequence contains word element
dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
}
else
{
dp[i + 1][j + 1] = dp[i][j + 1];
}
j += 1;
}
i += 1;
}
// Display given data
print("\n Sequence : " + sequence);
print("\n Word : " + word);
// Display calculated result
print("\n Result : " + dp[n][m]);
}
}
fun main(args: Array < String > ): Unit
{
val task: Subsequence = Subsequence();
val sequence: String = "initcometipe";
val word: String = "ice";
/*
sequence : initcometipe
word : ice
------------------
initcometipe
- - - ➀ [ice]
initcometipe
- - - ➁ [ice]
initcometipe
- - - ➂ [ice]
initcometipe
- - - ➃ [ice]
-------------------------------
4 possible sequence
*/
task.distinctSubsequences(sequence, word);
}
Output
Sequence : initcometipe
Word : ice
Result : 4
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