LeetCode 1092 Shortest Common Supersequence - Implementation

with reconstruction:

function shortestCommonSupersequence(str1, str2)
    m := length of str1
    n := length of str2
    dp := 2D array (m + 1) x (n + 1), all 0
    for i from 1 to m
        for j from 1 to n
            if str1[i - 1] = str2[j - 1] then
                dp[i][j] := dp[i - 1][j - 1] + 1
            else
                dp[i][j] := max(dp[i - 1][j], dp[i][j - 1])
    // Reconstruct SCS by backtracking through LCS
    result := empty string
    i := m, j := n
    while i > 0 and j > 0
        if str1[i - 1] = str2[j - 1] then
            result := str1[i - 1] + result
            i--
            j--
        else if dp[i - 1][j] > dp[i][j - 1] then
            result := str1[i - 1] + result
            i--
        else
            result := str2[j - 1] + result
            j--
    // Add remaining characters
    while i > 0
        result := str1[i - 1] + result
        i--
    while j > 0
        result := str2[j - 1] + result
        j--
    return result

Time: $O(mn)$. Space: $O(mn)$.

You first compute LCS, then backtrack. When characters match (part of LCS), add once. Otherwise, add the character you're moving away from.