Leetcode 1170 Solution

This article provides solution to leetcode question 1170 (shortest-common-supersequence)

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]