// function to generate all subsequences of given array function generate_subseq(arr): // length of arr n = len(arr) // total subsequences for array of length n m = 2**n // to store all subsequences seqs = [] // running a loop for m times for i in range(1, m): // creating an array of zeros of length n a = [0]*n num = i // to use as an index for 'a' j = n-1 // run this loop till num > 0 while num > 0: if num is odd: a[j] = 1 // divide num by 2 num = num/2 // subtract 1 from 'j' j -= 1 // to store current subsequence seq = [] // iterating for n times for i in range(n): // add ith index value to 'seq' if a[i] == 1: seq.append(arr[i]) // add 'seq' to 'seqs' seqs.append(seq) // return seqs return seqs // given lists S1 = ['B','C','D','A','A','C','D'] S2 = ['A','C','D','B','A','C'] // all non-empty subsequences of S1 seqs1 = generate_subseq(S1) // all non-empty subsequences of S2 seqs2 = generate_subseq(S2) // to store longest common subsequence ans = "" // iterating each subsequence in seqs1 for seq1 in seqs1: // iterating each subsequence in seqs2 for seq2 in seqs2: // found match and length of current answer < length of seq1 if seq1 == seq2 and len(ans) < len(seq1): // updating answer ans = seq1 // printing longest common subsequence print("Longest Common Subsequence: ", ans) Convert the above code to java code?
// function to generate all subsequences of given array
function generate_subseq(arr):
// length of arr
n = len(arr)
// total subsequences for array of length n
m = 2**n
// to store all subsequences
seqs = []
// running a loop for m times
for i in range(1, m):
// creating an array of zeros of length n
a = [0]*n
num = i
// to use as an index for 'a'
j = n-1
// run this loop till num > 0
while num > 0:
if num is odd:
a[j] = 1
// divide num by 2
num = num/2
// subtract 1 from 'j'
j -= 1
// to store current subsequence
seq = []
// iterating for n times
for i in range(n):
// add ith index value to 'seq'
if a[i] == 1:
seq.append(arr[i])
// add 'seq' to 'seqs'
seqs.append(seq)
// return seqs
return seqs
// given lists
S1 = ['B','C','D','A','A','C','D']
S2 = ['A','C','D','B','A','C']
// all non-empty subsequences of S1
seqs1 = generate_subseq(S1)
// all non-empty subsequences of S2
seqs2 = generate_subseq(S2)
// to store longest common subsequence
ans = ""
// iterating each subsequence in seqs1
for seq1 in seqs1:
// iterating each subsequence in seqs2
for seq2 in seqs2:
// found match and length of current answer < length of seq1
if seq1 == seq2 and len(ans) < len(seq1):
// updating answer
ans = seq1
// printing longest common subsequence
print("Longest Common Subsequence: ", ans)
Convert the above code to java code?
Step by step
Solved in 2 steps
