educative.io

Space optimization question

Courses
,
#1

Can we use 1D array for space optimization? I wonder if my code is correct:

def find_LCS_length_opt(s1, s2):
    n1, n2 = len(s1), len(s2)
    dp = [0 for _ in range(n2+1)]
    max_len = 0
    for i1 in range(1, n1+1):
        for i2 in range(n2, 0, -1):
            dp[i2] = 0
            if s1[i1-1] == s2[i2-1]:
                dp[i2] = 1 + dp[i2-1]
                max_len = max(max_len, dp[i2])
    return max_len
#2

Hi @Jing

Yes, we can use 1D array for space optimization. We appreciate your effort and your code is working perfectly fine.

Happy learning,

#3

Thank you!