# Edit Distance using Dynamic Programming (DP)

**Edit Distance using Dynamic Programming:** Given two string s1 and s2 of length M and N respectively, we have to perform 1) Insert a character at any position, 2) Delete a character at any position, and 3) Replace a character with any character at any position.

Submitted by Ritik Aggarwal, on December 09, 2018

**Problem:** You are given two strings ** s1** and

**of length**

*s2***and**

*M***respectively. You can perform following operations on the string.**

*N*- Insert a character at any position
- Delete a character at any position
- Replace a character with any character at any position

Find minimum number of ways to convert ** s1** into

**using above operation only.**

*s2***Constraints:**

1 <= N <= 2000

1 <= M <= 2000

**Example:**

Sample Input 1: abcde bcdae Sample Output 1: 2 Sample Input 2: dacef cdafe Sample Output 2: 3

**Explanation of the problem:**

In the first sample provided above, we can delete a from s1 and insert it before e in s1. So, there are two steps.

**Solution:**

Before proceeding to the solution we can see that the recursive solution will be hard to implement so we will proceed to the dynamic programming approach. In this approach, the **j ^{th}** cell of

**i**row represents the minimum number of changes needed to change s1(

^{th}**i**index to end) and s2(

^{th}**j**index to end). Now if an

^{th}**i**character of s1 is equal to a

^{th}**j**character of s2 then we don’t have to take care of that character as it is already same so pick up the right-bottom diagonal value. If characters are not equal then we can delete the

^{th}**i**character of the s1 or

^{th}**j**character of s2, replace the

^{th}**i**character of s1 with the

^{th}**j**character of s2 or vice versa and move on to the right bottom corner. In this case, we also have to add 1 as deletion, replacement is considered as a step.

^{th}**Algorithm:**

- Create dp matrix in which
**j**cell of^{th}**i**row represents the minimum number of ways to change the string^{th}**s1**(from**i**index to last) and string^{th}**s2**(**j**index to last).^{th} - One extra row and col are taken to build to include blank string also.
- If
**s1**is blank and**s2**is full we have to initialize this condition so initializing this condition doing the same thing for vice versa case. - Start filling dp matrix from the
**N**row and^{th}**M**column (right to left and down to up).^{th} - Find the answer of each row by using dp relations.
- If
**i**character of^{th}**s1**is same as a**j**character of^{th}**s2**then store the right-bottom value. - Otherwise, take the minimum of downward adjacent, rightward adjacent, bottom-right adjacent value and add 1 to it and store the answer.
- Store the answer in a
**j**cell of an^{th}**i**row.^{th}

**The time complexity of the above code is O (N * M).**

## C++ Code for Edit Distance using Dynamic Programming (DP)

#include <iostream> #include <math.h> using namespace std; // function for finding edit distance int editDistance(string s1, string s2){ // dp matrix for storing the values int dp[s1.length() + 1][s2.length() + 1] = {0}; int counter = 0; // loops are used to store some values necessary for dp relations as // we can initialize all values to 0 in this case for(int row = s1.length();row>=0;row--){ dp[row][s2.length()] = counter; counter++; } counter = 0; for(int col = s2.length();col>=0;col--){ dp[s1.length()][col] = counter; counter++; } // filling the dp matrix for(int row = s1.length()-1;row>=0;row--){ for(int col = s2.length() - 1;col>=0;col--){ // if rowth character of s1 is same as colth character of s2 // then store diagonally right-bottom shifted value if(s1[row] == s2[col]){ dp[row][col] = dp[row+1][col+1]; } // otherwise, take minimum of adjacent downward, adjacent rightward, // diagonally rigth-bottom value and add 1 to it and store that value else{ dp[row][col] = min(dp[row+1][col], min(dp[row][col+1], dp[row+1][col+1])) + 1; } } } return dp[0][0]; } // driver function to test the code int main() { string s1,s2; cin >> s1 >> s2; cout << s1 << "\n" << s2 << endl; cout<< editDistance(s1, s2); return 0; }

**Output**

abcde bcdae abcde bcdae 2

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions