#533 Build a Line Diff

A code review page shows a diff between oldLines and newLines. Each output row is a line with a two-character prefix: " " (two spaces) for a line kept from both versions, "- " for a line removed from the old version, and "+ " for a line added in the new version. The kept lines must be a longest common subsequence of the two versions, so the diff has as few - and + rows as possible.

Several diffs can be equally short, so build it with these rules. Keep two positions, i in oldLines and j in newLines, both starting at 0. While lines remain: if oldLines[i] === newLines[j], output a kept row and move both. Otherwise, if no new lines remain, or removing oldLines[i] still allows the longest number of kept lines for the rest (compared with adding newLines[j]), output a - row and move i; prefer - when both choices are equally good. Otherwise output a + row and move j.

Write buildDiff(oldLines, newLines) that returns the rows as an array of strings.

Input: oldLines = ["<ul>","<li>Home</li>","<li>Blog</li>","</ul>"], newLines = ["<ul>","<li>Home</li>","<li>Docs</li>","</ul>"]
Output: ["  <ul>","  <li>Home</li>","- <li>Blog</li>","+ <li>Docs</li>","  </ul>"]

Input: oldLines = [], newLines = ["x"]
Output: ["+ x"]

Constraints

• 0 <= oldLines.length, newLines.length <= 500
• Each line has at most 80 characters.