# 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

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!