Question

OpenSooq Assignment - Software Engineer
Given two strings input of printable text, a and b .
let the edit distance between a and b is least number of operations needed to transform a to
b, write php code that calculate edit distance using:
1. hamming distance that only have substitute operations (ex. substitute letter
X with letter Y).
2. Levenshtein distance: that have 3 possible operators: insert, delete or
substitution operations
the function should consider all possibilities but should not consider the same part twice, and
report the smallest possible distance
hamming_dis(a, b) returns integer levenshtein_dis(a,
b) returns integer
Your code should use the following:
1. OOP
2. two classes one for each mode hamming or levenshtein
2. one public static helper that creates an instance, initialise the state,
do the calculation and return the result
3. define protected/private properties as needed to hold input
strings and intermediate data that you use
5. private/protected methods that you call recursively if needed
6. those methods should take offset from the beginning of input texts
instead of passing substrings
7. document/comment your code
8. write another file that requires your file as a library and perform some tests on
it
9. write another command line tool that prompt for two input strings and
display the levenshtein distance
10. write a web page with a form of two fields and returns the
levenshteindistance, provide instructions to run it using PHP's builtin web server
from command line
example levenshtein distances a:
"this is a test"
b: "this is test"
levenshtein: 2 operations (remove a and next space)
a: "this is test" b:
"the is test"
levenshtein: 2 operations (replace i with e in this and remove s)

in python code please

Answer 1

//Import the necessary libraries
import java.util.*;
import java.util.Arrays;
//creating class
class edit_dist
{
   //Function to calculate Hamming Distance
   public static int hamming_Distance(String s1, String s2)
   {
       int count=0;
       for(int i=0;i<s1.length();i++)
       {
           if(s1.charAt(i)!=s2.charAt(i))
           {
               count++;
           }
       }
       return count;
   }
   //Function to calculate Levenshtein Distance  
   public static int levenshtein_Distance(String s1, String s2)
   {
       //initilize the lengths
       int len_s1=s1.length();
       int len_s2=s2.length();
       //Initilize the arrya of matrix for memorization
       int dp[][]=new int[len_s1+1][len_s2+1];
       for(int i=0;i<=len_s1;i++)
       {
           for(int j=0;j<=len_s2;j++)
           {
               if(i==0)
               {
                   dp[i][j]=j;
               }
               else if(j==0)
               {
                   dp[i][j]=i;
               }
               else
               {
                   dp[i][j]=minimum(dp[i-1][j-1]+(s1.charAt(i-1)==s2.charAt(j-1)?0:1),dp[i-1][j]+1, dp[i][j-1]+1);
               }
           }
       }
       return dp[len_s1][len_s2];
   }
   //Supporting Function for Levenshtein Distance
   public static int minimum(int... num)
   {
       return Arrays.stream(num).min().orElse(Integer.MAX_VALUE);
   }
   //Main Function
   public static void main(String args[])
   {
       //Hamming Distance

       String s1="hamming distance";
       String s2="hammanh distamcs";
       System.out.println("String 1:"+s1);
       System.out.println("String 2:"+s2);
       System.out.println("Hamming Distance : "+hamming_Distance(s1,s2));

       //Levenshtein Distance

       s1="this is test";
       s2="the is test";
       System.out.println("String 1:"+s1);
       System.out.println("String 2:"+s2);
       System.out.println("Levenshtein Distance : "+levenshtein_Distance(s1,s2));
   }
}