Edit Distance Java

PROGRAM TO FIND MINIMUM NUMBER OF EDITS REQUIRED TO CONVERT STRING


import java.util.*;
class GFG
{
   
static int minDis(String s1, String s2,
                  int n, int m, int[][]dp)
{
         
  // If any String is empty,
  // return the remaining characters of other String
  if(n == 0)   
    return m; 
  if(m == 0)   
    return n;
              
  // To check if the recursive tree
  // for given n & m has already been executed
  if(dp[n][m] != -1)   
    return dp[n][m];
                 
  // If characters are equal, execute
  // recursive function for n-1, m-1
  if(s1.charAt(n - 1) == s2.charAt(m - 1))
  {          
    if(dp[n - 1][m - 1] == -1)
    {              
      return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);          
    }       
    else
      return dp[n][m] = dp[n - 1][m - 1];  
  }
   
  // If characters are nt equal, we need to
           
  // find the minimum cost out of all 3 operations.     
  else
  {          
    int m1, m2, m3;        // temp variables  
    if(dp[n-1][m] != -1)
    {   
      m1 = dp[n - 1][m];     
    }          
    else
    {  
      m1 = minDis(s1, s2, n - 1, m, dp);     
    }           
             
    if(dp[n][m - 1] != -1)
    {               
      m2 = dp[n][m - 1];           
    }           
    else
    {   
      m2 = minDis(s1, s2, n, m - 1, dp);     
    }                                  
    
    if(dp[n - 1][m - 1] != -1)
    {   
      m3 = dp[n - 1][m - 1];     
    }  
    else
    {  
      m3 = minDis(s1, s2, n - 1, m - 1, dp);      
    }    
    return dp[n][m] = 1 + Math.min(m1, Math.min(m2, m3));       
  }
}
 
// Driver program
public static void main(String[] args)
{
     
  String str1 = "voldemort";
  String str2 = "dumbledore";
       
  int n= str1.length(), m = str2.length();   
  int[][] dp = new int[n + 1][m + 1];
  for(int i = 0; i < n + 1; i++)
  Arrays.fill(dp[i], -1);               
  System.out.print(minDis(str1, str2, n, m, dp));
}
}

OUTPUT:
7

Comments

Post a Comment

Popular posts from this blog

Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU # A Utility Function to print the Grid def print_grid(arr):      for i in range ( 9 ):          for j in range ( 9 ):              print arr[i][j],          print ( 'n' )              # Function to Find the entry in # the Grid that is still  not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list  variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l):      for row in range ( 9 ):       ...
Read more

Solve the Sudoku Java

PROGRAM TO SOLVE SUDOKU class GFG {      public static boolean isSafe( int [][] board,                                   int row, int col,                                   int num)      {          // Row has the unique (row-clash)          for ( int d = 0 ; d < board.length; d++)          {                             // Check if the number we are trying to   ...
Read more

Find Duplicates Java

PROGRAM TO FIND REPEATING NUMBERS IN AN ARRAY class MAIN {           public static void main(String args[]) {          int numRay[] = { 0 , 4 , 3 , 2 , 7 , 8 , 2 , 3 , 1 };               for ( int i = 0 ; i < numRay.length; i++) {              numRay[numRay[i] %  numRay.length] = numRay[numRay[i] %  numRay.length] + numRay.length;          }          System.out.println( "The repeating elements are : " );          for ( int i = 0 ; i < numRay.length; i++) {              if (numRay[i] >= numRay.length* 2 ) {                ...
Read more