A dynamic programming approach to this problem is described below. This approach takes O(n*n) time since we are comparing the letters of a string using an n*n matrix (where n is the length of the longer string since empty characters are added to the shorter string).
A dynamic programming approach to this problem is described below. This approach takes O(n*n) time since we are comparing the letters of a string using an n*n matrix (where n is the length of the longer string since empty characters are added to the shorter string).
(click on the image to be taken to the video)
Now that we know how to think about this programming from a dynamic programming perspective, we can write some code to solve the problem. There are a few different approaches to this but generally they all have some things in common:
- you will have a 2-d array that represents the matrix which compares