Take the recursive Java program Levenshtein.java and convert it to the equivalen

Question

 Take the recursive Java program Levenshtein.java and convert it to the equivalent C program. public class Levenshtein {      private static int testsFailed = 0;     private static int testsExecuted = 0;      public static void main( String[] args )     {         System.out.println( "Testing typical cases. " );         testDistance( "kitten", "kitten", 0 );         testDistance( "kitten", "sitting", 3 );         testDistance( "kitten", "mittens", 2 );         testDistance( "balloon", "saloon", 2 );         testDistance( "hello", "doggo", 4 );         testDistance( "		hi", "				hi", 2 );          System.out.println( " Testing empty/edge cases. " );         testDistance( "", "", 0 );         testDistance( "hello", "", 5 );         testDistance( "", "doggo", 5 );         testDistance( "a", "b", 1 );         testDistance( "b", "b", 0 );         testDistance( " ", " ", 0 );          System.out.println( " This might take a while... " );         testDistance( "12345678901", "123456789012", 1 );   // how many chars are we looking at?          System.out.println( " These tests will be opposite in the C version " );         testDistance( "kitten", "mittens", 3 );           // ????         testDistance( "totally", "different", 9 );          System.out.println( " Total number of tests executed: " + testsExecuted );         System.out.println( "Number of tests passed: " + (testsExecuted - testsFailed) );         System.out.println( "Number of tests failed: " + testsFailed );     }      public static void testDistance( String s, String t, int expected )     {         int distance = levenshtein( s, t );          if ( distance == expected )         {             System.out.println( "Passed! You can get from '" + s + "' to '" + t + "' in " + expected + " moves." );         }         else         {             System.out.println( "FAILED: I thought it would take " + expected + " moves, but apparently it takes " + distance +                      " moves to get from '" + s + "' to '" + t + "'." );             testsFailed++;         }          testsExecuted++;     }       public static int levenshtein( String s, String t )     {         int cost;         int distance;         String deleteS;         String deleteT;          if (s.length() == 0)         {             distance = t.length();         }         else if (t.length() == 0)         {             distance = s.length();         }         else         {             if (s.charAt(0) == t.charAt(0))             {                 cost = 0;             }             else             {                 cost = 1;             }              deleteS = s.substring(1);             deleteT = t.substring(1);              assert(deleteS.length() == s.length() - 1);             assert(deleteT.length() == t.length() - 1);              assert(s.endsWith(deleteS));              assert(t.endsWith(deleteT));              distance = minimum(levenshtein(deleteS, t) + 1,                                levenshtein(s, deleteT) + 1,                                levenshtein(deleteS, deleteT) + cost);         }          return distance;     }      public static int minimum( int... minimum ) // varargs! see: https://docs.oracle.com/javase/8/docs/technotes/guides/language/varargs.html     {         int min = 0;         assert( minimum.length > 0 );          if ( minimum.length > 0 )         {           min = minimum[0];            for ( int i = 1; i < minimum.length; i++ )           {               if ( minimum[i] < min )               {                   min = minimum[i];               }           }         }          return min;     } } 

Explanation / Answer

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int min(int x, int y, int z)
{
if((x < y)&&(x < z))
return x;
else
{
if(y < z)
return y;
else
return z;
}
}

int editDist(char str1[] , char str2[] , int m ,int n)
{
  
if (m == 0) return n;

if (n == 0) return m;

if (str1[m-1] == str2[n-1])
return editDist(str1, str2, m-1, n-1);


return 1 + min ( editDist(str1, str2, m, n-1), // Insert
editDist(str1, str2, m-1, n), // Remove
editDist(str1, str2, m-1, n-1) // Replace
);
}

int main()
{
char str1[]= "kitten";
char str2[] = "sitting";

printf("%d ", editDist( str1 , str2 , strlen(str1), strlen(str2)));

return 0;
}

===============================================

akshay@akshay-Inspiron-3537:~/Chegg$ gcc dista.c
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
3

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.