In this HackerRank The Longest Common Subsequence problem solution You have given two sequences of integers, A = [a[1], ... , a[n]] and B = [b[1],....,b[m]], find the longest common subsequence and print it as a line of space-separated integers. If there are multiple common subsequences with the same maximum length, print any one of them.
Problem solution in Python.
#!/bin/python3
import sys
# parse input
n,m = input().strip().split(' ')
n = int(n)
m = int(m)
A = [int(x) for x in input().strip().split(' ')]
B = [int(x) for x in input().strip().split(' ')]
# initialize table for DP
table = dict()
for i in range(0,n+1):
loc = tuple([i,0])
table[loc] = list()
for j in range(0,m+1):
loc = tuple([0,j])
table[loc] = list()
# populate table
for i in range(1,n+1):
for j in range(1,m+1):
a = A[i-1]
b = B[j-1]
if a == b:
seq = table[tuple([i-1,j-1])].copy()
seq.append(a)
table[tuple([i,j])] = seq
else:
ti = table[tuple([i-1,j])].copy()
tj = table[tuple([i,j-1])].copy()
if len(ti) > len(tj):
table[tuple([i,j])] = ti.copy()
else:
table[tuple([i,j])] = tj.copy()
# output result
out = table[tuple([n,m])]
out = ' '.join(str(x) for x in out)
print(out)
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = scanner.nextInt();
}
int[] b = new int[m];
for (int i = 0; i < m; ++i) {
b[i] = scanner.nextInt();
}
int[][] opt = new int[n + 1][m + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i - 1] == b[j - 1]) {
opt[i][j] = opt[i - 1][j - 1] + 1;
} else {
opt[i][j] = Math.max(opt[i][j - 1], opt[i - 1][j]);
}
}
}
//System.out.println(opt[n][m]);
int i = n, j = m;
Stack<Integer> stack = new Stack<>();
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) {
stack.push(a[i - 1]);
i -= 1;
j -= 1;
} else if (opt[i][j - 1] >= opt[i - 1][j]) {
j -= 1;
} else if (opt[i][j - 1] < opt[i - 1][j]) {
i -= 1;
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop() + " ");
}
System.out.println(sb.toString().trim());
}
}Problem solution in C++.
#include <ios>
#include <iostream>
int dp[105][105] = {};
int parenti[105][105] = {};
int parentj[105][105] = {};
int arr1[105] = {};
int arr2[105] = {};
int n, m;
bool first = true;
int lcs(int i, int j)
{
if (i == -1) return 0;
else if (j == -1) return 0;
else if (dp[i][j] == -1)
{
if (arr1[i] == arr2[j])
{
dp[i][j] = lcs(i-1, j-1)+1;
parenti[i][j] = i-1;
parentj[i][j] = j-1;
}
else
{
if (lcs(i-1, j) > lcs(i, j-1))
{
dp[i][j] = lcs(i-1, j);
parenti[i][j] = i-1;
parentj[i][j] = j;
}
else
{
dp[i][j] = lcs(i, j-1);
parenti[i][j] = i;
parentj[i][j] = j-1;
}
}
}
return dp[i][j];
}
void print(int i, int j)
{
if (i != -1 && j != -1)
{
print(parenti[i][j], parentj[i][j]);
if (arr1[i] == arr2[j])
{
if (first) first = false;
else std::cout << " ";
std::cout << arr1[i];
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
for (int i = 0; i < 105; i++)
{
for (int j = 0; j < 105; j++)
{
dp[i][j] = -1;
parenti[i][j] = -1;
parentj[i][j] = -1;
}
}
std::cin >> n >> m;
for (int i = 0; i < n; i++) std::cin >> arr1[i];
for (int i = 0; i < m; i++) std::cin >> arr2[i];
lcs(n-1, m-1);
print(n-1, m-1);
}Problem solution in C.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int* longestCommonSubsequence(int a_size, int* a, int b_size, int* b, int *result_size) {
int memo[a_size + 1][b_size + 1];
// initialize table.
for (int i = 0; i <= a_size; i++)
memo[i][0] = 0;
for (int j = 1; j <= b_size; j++)
memo[0][j] = 0;
// Find the length of the longest substring
for (int i = 1, r = 0; i <= a_size; i++, r++)
for (int j = 1, c = 0; j <= b_size; j++, c++)
if (a[r] == b[c])
memo[i][j] = memo[i - 1][j - 1] + 1;
else
memo[i][j] = (memo[i - 1][j] > memo[i][j - 1]) ? memo[i - 1][j] : memo[i][j - 1];
// Read the memo backwards to find the LCS
int len = memo[a_size][b_size];
int r = a_size;
int c = b_size;
int* result = (int*)malloc(sizeof(int) * len);
while (len) {
if (a[r-1] == b[c-1]) {
--len;
--r;
--c;
result[len] = a[r];
}
else if (memo[r - 1][c] == len)
--r;
else
--c;
}
*result_size = memo[a_size][b_size];
return result;
}
int main() {
int n;
int m;
scanf("%i %i", &n, &m);
int *a = malloc(sizeof(int) * n);
for (int a_i = 0; a_i < n; a_i++) {
scanf("%i",&a[a_i]);
}
int *b = malloc(sizeof(int) * m);
for (int b_i = 0; b_i < m; b_i++) {
scanf("%i",&b[b_i]);
}
int result_size;
int* result = longestCommonSubsequence(n, a, m, b, &result_size);
for(int result_i = 0; result_i < result_size; result_i++) {
if(result_i) {
printf(" ");
}
printf("%d", result[result_i]);
}
puts("");
return 0;
}
0 Comments