0

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
Iain Shelvington
  • 26,159
  • 1
  • 24
  • 40

0 Answers0