Pattern visualizer
Shortest Common Supersequence
A supersequence must carry every letter of both strings, in order, but a letter both strings agree on at this position can be written ONCE and still count for both. Compare the last letters of the two prefixes: if they match, share that letter and fall back to the diagonal cell. If they differ, the supersequence has to spend a character on one of them alone, so take whichever neighbour (up or left) is cheaper and add one. The arrows in the table are exactly that choice, made visible. Animated on: str1 = "abac", str2 = "cab" — find the length of the shortest string that contains both as subsequences..
Share a letter when both strings agree, pay one character when they don't
rows = prefixes of "abac", columns = prefixes of "cab"
dp[i][j] is the shortest string containing both the first i letters of "abac" and the first j of "cab" as subsequences. Two empty prefixes need nothing, so dp[0][0] = 0.
1FUNCTION shortestCommonSupersequence(str1, str2)2 m <- LENGTH(str1)3 n <- LENGTH(str2)4 FOR i FROM 0 TO m5 dp[i][0] <- i6 FOR j FROM 0 TO n7 dp[0][j] <- j8 FOR i FROM 1 TO m9 FOR j FROM 1 TO n10 IF str1[i-1] = str2[j-1]11 dp[i][j] <- 1 + dp[i-1][j-1]12 ELSE13 dp[i][j] <- 1 + MIN(dp[i-1][j], dp[i][j-1])14 RETURN dp[m][n]
← / → step · space play · Home restart