How should I write this generic algorithm [closed]

Question

Suppose you have two strings. Each string has lines, seperated by a newline character. Now you want to compare both strings and then find the best method (shortest number of steps) by only adding or deleting lines of one string, to transform the second string in to the first string.

i.e.

string #2:

abc
def
efg
hello
123

and string #1:

abc
def
efg
adc
123

The best (shortest steps) solution to transform string #2 in to string #1 would be:

1. remove line at line position 3 ('hello')
2. add 'abc' after line position 3

How would one write a generic algorithm to find the quickest, least steps, solutions for transforming one string to another, given that you can only add or remove lines?

Answer 1

This is a classic problem.

For a given set of allowed operations the edit distance between two strings is the minimal number of operations required to transform one into the other.

When the set of allowed operations consists of insertion and deletion only, it is known as the longest common subsequence edit distance.

You'll find everything you need to compute this distance in Longest common subsequence problem.