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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
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