Edit Distances Top Down Recursive Dynamic Programming Explained in Python

The question asks us to convert string S to string T with MINIMUM possible operations.The operations include INSERTION,DELETION and REPLACEMENT.

Thinking recursively first:

Base condition: The smallest possible input would be empty string S and non empty string T or empty string T and non empty string S.In the former case,we need to delete the remaining characters from string T inorder to make it equal to string S.In the latter case we need to insert the character from string T into S.

After this,we check recursively check for each characters of string S and T using pointer indices i and j.If they are the same,both the pointers are moved

Else,we need to consider the 3 operations that could be done on the string S.

Deletion:If we delete a character from S,then its equivalent to moving only pointer i

Insertion:If we insert an character into S,its equivalent to moving only pointer j

Replacement:If we replace an character in S,its equivalent of moving both pointers i and j

Each of this is an operation.

Performing each of this operation on the string,we call the function recursively on the remaining string. Since this is a minimization problem,we need to choose the operation that would yield the most minimum operations on the string in the future.

We also see that there is overlapping sub problems in this.The value of pointer i and j repeat for smaller sub problems and we calculate them again and again even though we have already calculated it. This can be exploited to increase performace by caching these in a hashap using <i,j> as the key.

In code this would look like: