Tale of a dynamic programming problem

We are gonna discuss about the approach to solve a common dynamic programming problem

Problem Statement :

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character

Delete a character

Replace a character

Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3

Explanation: horse -> rorse (replace ‘h’ with ‘r’)rorse -> rose (remove ‘r’)rose -> ros (remove ‘e’)

Example 2: Input: word1 = “intention”, word2 = “execution” Output: 5

Explanation: intention -> inention (remove ‘t’)inention -> enention (replace ‘i’ with ‘e’)enention -> exention (replace ’n’ with ‘x’)exention -> exection (replace ’n’ with ‘c’)exection -> execution (insert ‘u’)

Step by step solution to the problem :

Now to decide a problem can be solved by dynamic programming or not we have to observe if it has mainly two properties :1)Overlapping Subproblems 2)Optimal Substructure.

For this problem if we observe carefully at every step you have 3 choices that can lead to solution and in next step we can again perform these 3 operations on the result obtained by best choice of the previous step. This feature of this problem maps to Optimal Substructure of dynamic programming.

We will try to solve the problem using bottom up approach of dynamic programming i.e. we will start from solving small modules and add them up together.

Corner cases : If any one of the word is null or empty, each step we have no choice other than doing add operation. So the answer will be length of the non empty word.Below is the code for same

if(word1==null || word1.length()==0) return word2.length(); if(word2==null || word2.length()==0) return word1.length();

Base cases : Now we write below lines where dp[i][j] signifies no of operations to convert word1 of length i to word2 of length j.

int len1=word1.length(); 
int len2=word2.length(); 
int[][] dp=new int[len1+1][len2+1]; 
for(int i=1;i<=len1;i++)dp[i][0]=i;
for(int j=1;j<=len2;j++)dp[0][j]=j;

dp[0][0] = 0 as we don’t need any operations to convert “” to “”.

for(int i=1;i<=len1;i++)dp[i][0]=i; this line signifies that if our first word has x character and second one is empty, we have to delete x character from the first word to get second word.

for(int j=1;j<=len2;j++)dp[0][j]=j; this line signifies that if our first word is empty and second word has x character , we have to add x character from the first word to get second word.

Main Logic :

for(int i=1;i<=len1;i++){
  for(int j=1;j<=len2;j++){ 
     if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
     else dp[i][j]=1+Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),     dp[i][j-1]);
    }
 }

Now if both the character of the current index of two word matches, there is no action needed so we can easily say this state data is equal to previous state data. If they don’t match then we need to do one operation in this step for sure. Let’s say c = word1.charAt(i-1), d =word2.charAt(j-1);

dp[i][j]=1+dp[i-1][j-1] if we choose to replace c with d

dp[i][j]=1+dp[i-1][j] if we choose to add d after c

dp[i][j]=1+dp[i][j-1] if we choose to delete c

As we have to get minimum no of operations we take minimum of (dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) +1to get the result.

The complete code for this problem can be found in https://github.com/GyanTech877/algorithms/blob/master/dynamicprogramming/EditDistance.java.

Happy Learning 😎