Leetcode 1170 Solution

This article provides solution to leetcode question 1170 (shortest-common-supersequence)
Categories:
Tags:
Access this page by simply typing in "lcs 1170" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/shortest-common-supersequence

Solution

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        if len(str1) == 0:
            return str2
        if len(str2) == 0:
            return str1

        dp = [0] * len(str2)

        for i in range(len(str1)):
            last_dp = list(dp)

            for j in range(len(str2)):
                ch1 = str1[i]
                ch2 = str2[j]

                if ch1 == ch2:
                    if i == 0:
                        dp[j] = str2[:j + 1]
                    elif j == 0:
                        dp[j] = str1[:i + 1]
                    else:
                    	dp[j] = last_dp[j - 1] + ch1 if j > 0 else str1[:i + 1]
                else:
                    candidates = []
                    if i > 0 and j > 0:
                    	candidates.append(last_dp[j] + str1[i])
                    	candidates.append(dp[j - 1] + str2[j])
                    elif i > 0:
                    	candidates.append(last_dp[j] + str1[i])
                    elif j > 0:
                    	candidates.append(dp[j - 1] + str2[j])
                    else:
                        candidates.append(str1[i] + str2[j])

                    dp[j] = sorted(candidates, key=lambda x: len(x))[0]

        return dp[-1]