[백준] 9251번: LCS

https://www.acmicpc.net/problem/9251

initial

So we are given 2 strings and we want to find the longest common subsequence (LCS). We have encountered Longest increasing subsequence (LIS) of 2 lists of integers but now it is 2 strings. I was trying to find out the pattern of this but even when I got the hint of dp, I was using a 1d dp list. We can’t use just 1d dp list cuz we need previous state of the previous row and column (dp[i-1][j-1]). I always have trouble thinking up of idea to use 2d dp table. I should have noticced when we are given just 2 inputs so 2d dp table could have been an option

revisited june 3rd

dp table should be this, not the image below

wrong: but correct explanation of slicing

Let dp[i][j] be the maximum length of subsequence when we are comparing sliced string1 from index 0 to i and sliced string2 from index 0 to j. The dp table will have 0s initialised and especially in first row and column cuz when we do [i-1][j-1] we need that 0 value. If we encounter the same character from both strings, we do dp[i-1][j-1]+1 cuz this is the pattern. Not much to explain but literally this is the pattern. Else, we take the max value of dp[i-1][j] and dp[i][j-1] cuz we can build upon that maximum subsequence later on when we encounter same character in next iter i.

solution

hola1 = input()
hola2 = input()

# Initialize the DP table with zeros
dp = [[0 for _ in range(len(hola2) + 1)] for _ in range(len(hola1) + 1)]

for i in range(1, len(hola1) + 1):
    for j in range(1, len(hola2) + 1):
        if hola1[i - 1] == hola2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[-1][-1])

IMPT print subsequence as well

This is trickier. Tracing back the LCS is trickier. We start from the bottom right of our dp table and if we have the same character from string1 and string2 at pointer i and j, we append that character to our temporary list. Else, we choose the bigger value of [i-1][j] and [i][j-1] and decrement our i,j pointers accordingly to hopefully reach a combination of i and j where string1[i] and string2[j] has same character. At the end, reverse the list and combine it as a string.

# Trace back to find the LCS
lcs = []
i, j = len(hola1), len(hola2)
while i > 0 and j > 0:
    if hola1[i - 1] == hola2[j - 1]:
        lcs.append(hola1[i - 1])
        i -= 1
        j -= 1
    elif dp[i - 1][j] > dp[i][j - 1]:
        i -= 1
    else:
        j -= 1

# Reverse the LCS to get the correct order
lcs = ''.join(reversed(lcs))

time and space

n^2 time and space