# input: a[0..M) and b[0..N), M>=0 and N>=0## output: length of a longest common subsequence of a[0..M) and# b[0..N)## O(MN) time and O(N) space solutiondeflcs_tab_opt(a,b):M,N=len(a),len(b)tab=[[0forninrange(N+1)]forminrange(2)]m,n,prev,curr=1,1,0,1whilem!=M+1:ifn==N+1:m,n,prev,curr=m+1,1,1-prev,1-currelse:ifa[m-1]==b[n-1]:tab[curr][n]=1+tab[prev][n-1]else:tab[curr][n]=max(tab[curr][n-1],tab[prev][n])n+=1returntab[prev][N]
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.