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: . Space: .
You first compute LCS, then backtrack. When characters match (part of LCS), add once. Otherwise, add the character you're moving away from.