How would you write a \"memoized\", iterative version of the longest common subs

Question

How would you write a "memoized", iterative version of the longest common subsequence algorithm?

A memoized, recursive version looks as follows:

def lcsLena (X,Y): gamma make Table (len (X)+1 len (Y)+1) #cache for length values, with extra 0th row & column. return c(X,Y,len (x),len (Y) ,gamma) def c cache) if cache Ci] [j None if i 0 or j 0: cache [i] Cj] 0 elif xli-1] YDj-1]: We need to offset both i and j, because of the extra values cache [i] Cj] c (x,Y,i-1,j-1, cache 1 else a c cache) b c(x,Y,i, j 1, cache) if a b: cache [i] [1] a else cache [i] Cj] b return cache Llen(X)] Clen (Y)]

Explanation / Answer

def lcs(X , Y):

x_len = len(X)
y_len = len(Y)

cache = [[None]*(y_len+1) for i in range(0, x_len+1)]

for i in range(0, x_len+1):
for j in range(0, y_len+1):
if i == 0 or j == 0 :
cache[i][j] = 0
elif X[i-1] == Y[j-1]:
cache[i][j] = cache[i-1][j-1]+1
else:
cache[i][j] = max(cache[i-1][j] , cache[i][j-1])

return cache[x_len][y_len]

# code link: https://paste.ee/p/NMMzr

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.