Leetcode Problem 1143. Longest Common Subsequence

1143. Longest Common Subsequence

Leetcode Solutions

Dynamic Programming with Space Optimization

  1. Initialize two arrays, previous and current, each with a length equal to the length of the shorter string plus one, filled with zeros.
  2. Iterate over the characters of the longer string in reverse order, using an outer loop.
  3. For each character in the longer string, iterate over the characters of the shorter string in reverse order, using an inner loop.
  4. If the characters at the current positions in the two strings match, set current[j] to 1 + previous[j + 1].
  5. If the characters do not match, set current[j] to the maximum of previous[j] and current[j + 1].
  6. After completing the inner loop, swap previous and current arrays.
  7. The first element of the previous array after the last iteration will contain the length of the LCS.
UML Thumbnail

Memoization Approach

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...