String Transformation in Java using Dynamic Programming

In this Java tutorial, we are going to convert string1 to string2 using the minimum number of operations or string transformation in Java. So, we can either insert a character in string1 or remove a character or replace a character from string1.

Step by Step approach

Let’s see the step by step approach of string transformation in Java.

1. Read the two strings.
2. Create a table of (a+1)*(b+1) where a is the length of first string and b is the length of second string.
3. If the first string is empty, then we have only one option is to insert all characters of second string in string1.
4. If the second string is empty, then we have only one option is to remove all characters of the first string.
5. If the last character of both strings found equal, them remove it and recur for the remaining string.
6. If the last character found different , then we have to find the minimum value among inserting a character in string1, or removing a character from string1 or replacing a character and add one for the current operation.

Code Snippet to check minimum among inserting, removing and replacing

int min1=dp[i-1][j]>dp[i][j-1] ? dp[i][j-1] : dp[i-1][j] ;
int min2=dp[i-1][j-1]>min1 ? min1 : dp[i-1][j-1] ;
                            
         dp[i][j] = 1+min2;

Java Code for transforming string1 to string2

import java.util.Scanner;

class Codespeedy
{
    static int result(String s1 , String s2 , int a , int b)
    {
        int dp[][] = new int[a+1][b+1];
        
          for(int i=0;i<=a;i++)
          {
              for(int j=0;j<=b;j++)
               {
                   if(i==0)
                    dp[i][j]=j;
                    
                    else if(j==0)
                     dp[i][j]=i;
                     
                     else if(s1.charAt(i-1)==s2.charAt(j-1))
                         dp[i][j]=dp[i-1][j-1];
                         
                        else
                        {
                            int min1=dp[i-1][j]>dp[i][j-1] ? dp[i][j-1] : dp[i-1][j] ;
                            int min2=dp[i-1][j-1]>min1 ? min1 : dp[i-1][j-1] ;
                            
                              dp[i][j] = 1+min2;
                        }
               }
          }
        
        return dp[a][b];
    }
    
    public static void main(String args[])
    {
            Scanner scan = new Scanner(System.in);
            
           String s1 = scan.nextLine();
           String s2 = scan.nextLine();
           
            System.out.println( result( s1 , s2 , s1.length(), s2.length()) ); 
    }
}

INPUT

codespeedy
codetutorial

OUTPUT

8