Leetcode Problem 1092. Shortest Common Supersequence

1092. Shortest Common Supersequence

Leetcode Solutions

Dynamic Programming - Longest Common Subsequence (LCS) Approach

  1. Initialize a 2D array dp with dimensions (len(str1) + 1) x (len(str2) + 1) to store the lengths of LCS for substrings of str1 and str2.
  2. Fill the dp array using dynamic programming, where dp[i][j] represents the length of LCS of str1[:i] and str2[:j].
  3. Iterate over str1 and str2 using indices i and j, starting from the end of the strings.
  4. If characters str1[i] and str2[j] are equal, add this character to the LCS and move diagonally in the dp array.
  5. If not, move in the direction of the larger value in the dp array (either up or left).
  6. Continue this process until the entire dp array is traversed.
  7. The LCS will be constructed in reverse order.
  8. Iterate through the LCS and simultaneously through str1 and str2, adding characters to the result string.
  9. If a character from str1 or str2 is not part of the LCS, add it to the result string before the matching LCS character.
  10. After processing the LCS, append any remaining characters from str1 or str2 to the result string.
  11. Return the result string.
UML Thumbnail

Brute Force - Generate All Supersequences and Select the Shortest

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...