1
class Solution:
2
    def shortestCommonSupersequence(self, A, B):
3
        n, m = len(A), len(B)
4
        dp = [B[:i] for i in range(m + 1)]
5
        for i in range(n):
6
            prev = A[:i]
7
            dp[0] = A[: i + 1]
8
            for j in range(m):
9
                if A[i] == B[j]:
10
                    prev, dp[j + 1] = dp[j + 1], prev + A[i]
11
                else:
12
                    prev, dp[j + 1] = dp[j + 1], min(
13
                        dp[j] + B[j], dp[j + 1] + A[i], key=len
14
                    )
15
        return dp[-1]