Skip to the code
cf.
+50 XP

#714 Render a Line Diff

hard

Build the text of a line diff like the ones in code review. Write renderDiff(oldLines, newLines) that returns a list of output lines: " " + line for a kept line, "- " + line for a deleted line, and "+ " + line for an inserted line.

Many diffs are equally short, so follow this exact rule. Let lcs[i][j] be the length of the longest common subsequence of oldLines from index i and newLines from index j. Start with i = 0 and j = 0 and repeat until both lists are used up:

  • If both lines exist and are equal, keep it and move both i and j.
  • Otherwise, if newLines is used up, or oldLines isn't and lcs[i + 1][j] >= lcs[i][j + 1], delete oldLines[i] and move i.
  • Otherwise insert newLines[j] and move j.

Example 1

Input: oldLines = ["title","intro","body"], newLines = ["title","body","footer"]
Output: ["  title","- intro","  body","+ footer"]

intro is deleted and footer added; the other lines are kept.

Example 2

Input: oldLines = ["a"], newLines = ["b"]
Output: ["- a","+ b"]

On a tie, deleting comes first, so a changed line shows - then +.

Constraints

  • 0 <= oldLines.length, newLines.length <= 500
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).