Line-by-Line Diff

Version control tools show what changed in a file as a diff: the lines that stayed, the lines that were removed and the lines that were added. Write diff(old, new) that compares two lists of lines and returns the diff as a list of strings, where each line of the diff is:

• ' ' followed by the line, for a line kept from old in new
• '-' followed by the line, for a line of old that was removed
• '+' followed by the line, for a line of new that was added

Reading only the kept and removed lines of the diff gives old back, in order, and reading only the kept and added lines gives new. The diff must be as short as possible, which means keeping as many lines as possible.

Several shortest diffs often exist. Return the one you get by building it from the top of both files, one step at a time:

• If the next old line and the next new line are equal, keep it. (Keeping two equal lines never makes the diff longer.)
• Otherwise, remove the next old line, unless that would make the diff longer than the shortest possible; in that case, add the next new line.
• When one list is used up, the rest of the other list is removed or added.

Examples

diff(['a', 'b', 'c'], ['a', 'c', 'd'])  # returns [' a', '-b', ' c', '+d']
diff(['x'], ['y'])                      # returns ['-x', '+y']
diff(['b', 'a'], ['a', 'c', 'a'])       # returns ['-b', ' a', '+c', '+a']
diff([], ['p', 'q'])                    # returns ['+p', '+q']

In the third example ['-b', '+a', '+c', ' a'] is as short, but the rule removes "b" first and then keeps the first "a".

Constraints

• 0 <= len(old), len(new) <= 300
• Lines are strings and may be empty.