The Longest Common Subsequence Discussions | Algorithms | HackerRank

We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Python 3 solution, using dynamic program with a two dimensional table the size of the input arrays to store the length of longest subsequence, then trace back from the last square in the table to see where the matches where and eventually print all these matches (reversed) - that's the longest subsequence

input()a=[0]+[int(x)forxininput().split()]# to make first row/col of 0'sb=[0]+[int(x)forxininput().split()]# table will be the dynamic programming tabletable=[[0for_inrange(len(a))]for_inrange(len(b))]# populating tableforiinrange(1,len(b)):forjinrange(1,len(a)):ifa[j]==b[i]:table[i][j]=table[i-1][j-1]+1else:table[i][j]=max(table[i][j-1],table[i-1][j])# table[len(b)-1][len(a)-1] is the length of longest common subsequence# in order to find the subsequence we have to trace back from that square# see where the matches where and add them to word common_subsequencelength=table[len(b)-1][len(a)-1]common_subsequence=[]curr=len(b)-1,len(a)-1# save my current index in table in the searchwhilelength:ifb[curr[0]]==a[curr[1]]:# match - belongs to common subseqcommon_subsequence.append(b[curr[0]])length-=1curr=(curr[0]-1,curr[1]-1)else:# go to the square that has longer subsequence until nowiftable[curr[0]-1][curr[1]]>table[curr[0]][curr[1]-1]:curr=(curr[0]-1,curr[1])else:curr=(curr[0],curr[1]-1)print(' '.join(str(x)forxincommon_subsequence[::-1]))# reverse

## The Longest Common Subsequence

You are viewing a single comment's thread. Return to all comments →

Python 3 solution, using dynamic program with a two dimensional table the size of the input arrays to store the length of longest subsequence, then trace back from the last square in the table to see where the matches where and eventually print all these matches (reversed) - that's the longest subsequence