In an attempt to solve the longest common sub-sequence using memoization technique, I have "discovered" that my dictionary from the first function call gets passed to subsequent function calls and therefore does not execute subsequent function calls as intended.
def lcs_memoized(
seq1, seq2, index_of_seq1: int = 0, index_of_seq2: int = 0, memo: dict = {}
):
# create a key for the correspoding pointers
memo_key = (index_of_seq1, index_of_seq2)
# fetch the memo if the current pointers have been added
memo_value = memo.get(memo_key, None)
if memo_value: # checks if memo is not None
# print(f"Memo exists!key ==> {memo_key} value ==> {memo_value}")
print(id(memo))
return memo_value
# if the pointers are out of range, return 0, base case for exit.
elif index_of_seq1 == len(seq1) or index_of_seq2 == len(seq2):
print("Reached the end, will stop ...........")
memo[memo_key] = 0
# if the current seq are equal, increase count by one and move the pointers forward in the next recursive call.
elif seq1[index_of_seq1] == seq2[index_of_seq2]:
print("Found a match!")
memo[memo_key] = 1 + lcs_memoized(
seq1, seq2, index_of_seq1 + 1, index_of_seq2 + 1, memo
)
else:
# if the current elements are not equal, take the maximum from memoization of increased pointers.
memo[memo_key] = max(
lcs_memoized(seq1, seq2, index_of_seq1 + 1, index_of_seq2, memo),
lcs_memoized(seq1, seq2, index_of_seq1, index_of_seq2 + 1, memo),
)
# return the recently evaluated value.
item = memo.get(memo_key)
return item