Snippets

Camilo Rocha LCS with tabulation

Created by Former user
View revision

File lcs_tab.py Added

  • Ignore whitespace
  • Hide word diff 
+# 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 space solution
+
+def lcs_tab(a,b):
+  M,N = len(a),len(b)
+  tab = [ [ 0 for n in range(N+1) ] for m in range(M+1) ]
+  m,n = 1,1
+  while m!=M+1:
+    if n==N+1: m,n = m+1,1
+    else:
+      if a[m-1]==b[n-1]: tab[m][n] = 1+tab[m-1][n-1]
+      else: tab[m][n] = max(tab[m][n-1],tab[m-1][n])
+      n += 1
+  return tab[M][N]
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.