Redirecting to
NADOS


  Prev   Next

Edit Distance







Don't be a philosopher unless you achieve what you dreamt of!

Edit Distance

Welcome Back Reader!

In this article we will discuss about the next problem based on "Dynamic Programming" i.e. "Edit Distance".

Before you move any further, it is advised that you give this problem a fair try. Let's jump to the problem.


Important Links : Problem Link, Solution Video


Understanding the Problem:

In this problem you are given two strings s1 and s2.

All you have to do is find the minimum number of operations needed to convert s1 to s2.

Operations allowed are -

  • Insert -You can insert any character in s1.
  • Remove -You can remove any character in s1.
  • Replace -You can replace any character in s1 with any other character.


For example:

Sample Input:

pepperatcoding
pepcoding

Sample Output:

5



HOW?

To convert the string-1 'pepperatcoding' to string-2 'pepcoding' we need to delete 'perat' from 'pepperatcodding' to get 'pepcoding'. And to delete 'perat', 5 deletion operations are required.

For more clarity of the question, watch this part of the video.

Moving On:
  • To find the minimum number of operations which are needed to convert a string-1 to string-2 we can use various methods like recursion, memorization and tabulation.
  • Here we will solve it using Tabulation (dynamic Programming).
  • Let's take an example to understand the tabulation for this in a better way.
    For example: string-1: 'ahellobye' and string-2: 'amezooe'
  • So first of all we need a 2D array of size ((length of string-1) + 1) * ((length of string-1) + 1). We take one dimension extra to incorporate the case of empty strings.
  • String-1'ahellobye' corresponds to rows (y-axis) whereas String-2 'amezooe' corresponds to columns (x-axis). dp[i][j] at any position stores the minimum number of operations which are needed to make substring of string-1 from 0 to i similar to substring of string-2 from 0 to j.
  • Like dp[3][4] will store the minimum number of operations to make substring of string-1 from 0 to 3 i.e. 'ahe' is similar to substring of string-2 from 0 to 4 i.e. 'amez'.
    img
  • Talking of the first row; this is a special case. This row corresponds to the cases if string-1 is an empty string. Therefore with each increasing j the number of additional operations required will also increase linearly.
  • Similarly, for the first column; this is a special case too. This column corresponds to the cases if string-2 is an empty string. Therefore with each increasing i the number of deletion operations required will also increase linearly.
    img
  • Now we can start to fill the rest of the dp matrix. We will fill this row wise.
  • To fill the next row, first of all check if the characters at ith position of string-1 are the same as the jth character of string-2. If the characters are equal then the value for the dp[i][j] will be the same as dp[i-1][j-1].
  • And if the characters are not equal then we need to choose the minimum of dp[i-1][j-1], dp[i-1][j] and dp[i][j-1]. And then add 1 to the minimum among these.
    img
  • Final answer will be present at dp[n1.length-1][n2.length-1] i.e. dp[9][8].

For more clarity of this part and understand the why; watch this part of the video.

Let's try to code this!
img
  1. First of all we have captured the length of both the strings in variables n1 and n2 respectively and then defined a 2D array of size (n1+1) * (n2+1).
  2. Then we fill the first column of dp with a value same as the value of row using a for loop.
  3. Then we fill the first row of dp with a value the same as the value of the column using a for loop.
  4. After that we fill the rest of the dp matrix using a nested for loop.
  5. On entering a nested for loop, first of all check if the ith character of string-1 and jth character of string-2 equal. If yes, then store the same value at dp[i][j] which is present at dp[i-1][j-1].
  6. Otherwise add 1 to the minimum of dp[i-1][j-1], dp[i-1][j] and dp[i][j-1].
  7. And then at last return the final answer which will be stored at dp[n1.length-1][n2.length-1].

For more clarity of the code, watch this part of the video.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); String s1 = scn.next(); String s2 = scn.next(); System.out.println(solution(s1,s2)); } public static int solution(String str1, String str2) { int n1 = str1.length(); int n2 = str2.length(); int[][] dp = new int[n1 + 1][n2 + 1]; for (int i = 0; i <= n1; i++) { dp[i][0] = i; } for (int i = 0; i <= n2; i++) { dp[0][i] = i; } for(int i = 1; i <= n1; i++) { for(int j = 1; j <= n2; j++) { if(str1.charAt(i - 1) == str2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; }else { dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][ j - 1])) + 1; } } } return (dp[n1][n2]); } }
java; true";
Analysis
Time Complexity:

O(n1*n2)

A nested for loop is used to fill the dp matrix which takes time of O(n1*n2).

Space Complexity:

O(n1*n2)

One n1 x n2 sized 2D array is used which condenses to O(n1*n2).

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website. Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!

Happy Coding!

Edit Distance
Dynamic Programming and Greedy
Author: Nikita Aggarwal
 
Run
Id Name