Roviyas: java

Showing posts with label java. Show all posts

Thursday, March 2, 2017

Edit Distance Java Similar String

The edit distance of two strings commonly refers to the Levenshtein Distance of two strings- the amount of work it takes to transform one string to the other by either inserting, deleting, or changing one character at a time.

For example, changing sitting -> kitten takes 3
moves: sitting -> kitting, kitting -> kittin, and finally kittin -> kitten.

The algorithm to solve this in reasonable time takes dynamic programming, and has many applications such as word checking, and typing speed tests. Algorithm below:

public static int editDistance(String s, String t){
    int m=s.length();
    int n=t.length();
    int[][]d=new int[m+1][n+1];
    for(int i=0;i<=m;i++){
      d[i][0]=i;
    }
    for(int j=0;j<=n;j++){
      d[0][j]=j;
    }
    for(int j=1;j<=n;j++){
      for(int i=1;i<=m;i++){
        if(s.charAt(i-1)==t.charAt(j-1)){
          d[i][j]=d[i-1][j-1];
        }
        else{
          d[i][j]=min((d[i-1][j]+1),(d[i][j-1]+1),(d[i-1][j-1]+1));
        }
      }
    }
    return(d[m][n]);
}
public static int min(int a,int b,int c){
    return(Math.min(Math.min(a,b),c));
}

It is important to note that there are only three possibilities one string can get to another: either deleting, inserting, or changing.

Thus, if we let L(i,j) indicate the cost it takes from changing i to j, if s and t are the original strings, the cost is:

Math.min(1+L(i-1,j-1),1+L(i,j-1),1+L(i-1,j)) unless the last characters of the strings are the same, then the minimum is L(i-1,j-1). This solves the problem, but note that it is very slow because of all the recursive calls, which repeat many similiar problems.

Thus, we use dynamic programming: Construct a matrix d[m][n] with sizes s.length() and t.length(). instead of recursive calls, we will use a matrix lookup which will store the smallest current cost to change a smaller i into j.

Thus, with he java algorithm code for edit distance above, the speed is O(mn) where m and n are the sizes of the strings.

Available link for download

Dynamic Dispatch in Java

It is a concept in java to achieve the Dynamic / Run-time polymorphism. It is the process of assigning sub-class object in super type reference later if needed that sub-class object can be type-caste into its super type. Dynamic dispatch can be achieved only with the instance member.

Important point regarding dynamic dispatch

1. If we are trying to access instance member with dynamic dispatch concept then it will access sub-class overridden method.

2. If we are trying to access static member with the dynamic dispatch concept then it will access super-class method as because compiler internally replace the super-class reference variable with its class name.

Example showing dynamic dispatch with instance and static method.

class B {

 public static void display(){
 System.out.println("super-class static method");
 }
 public void add(){
 System.out.println("super-class instance method");
 }
}

public class A extends B{
 
 public static void display(){
 System.out.println("sub-class static method");
 }
 public void add(){
 System.out.println("sub-class instance method");
 }
 
 public static void main(String[] args) throws Exception {
 
 B b = new A(); // Dynamic dispatch 
 b.display(); // Calling static method
 b.add(); // Calling instance method
 }

}

In the above code the statement B b = new A() is used to store sub-class in its super-class and tried to access static method " display " which will super-class display() method as because compiler internally convert the b.display() into B.display() but in case of instance it will access with the object only thats why it call the overridden method in sub-class.

Note : The same will happen with the static and instance variable. With dynamic dispatch concept accessing static variable will access super-class static variable but accessing instance variable will access sub-class instance variable.

Available link for download

Thursday, March 2, 2017

Edit Distance Java Similar String

Edit Distance Java Similar String

Saturday, February 25, 2017

Dynamic Dispatch in Java

Dynamic Dispatch in Java