Spoj Problem EDIST - Edit Distance[Java Solution]

   Spoj Problem EDIST - Edit Distance[Java Solution]                                           

Problem Statement:-http://www.spoj.com/problems/EDIST/

Hint:- Dynamic Programming.

Java Program:-

/**
 * @(#)EDIST.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/11/2
 */

import java.io.*;


class EDIST {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    int T=Integer.parseInt(br.readLine());
   
    while(T--!=0){
   
    String str1=br.readLine();
    String str2=br.readLine();
   
    System.out.println(solve(str1,str2));
   
    }
   
    }  
 
    public static int solve(String s1,String s2){
    int ar[][]=new int[s1.length()+1][s2.length()+1];
    for(int i=0;i<=s1.length();i++){
    ar[i][0]=i;
    }
   
    for(int i=0;i<=s2.length();i++){
    ar[0][i]=i;
    }
   
    for(int i=1;i<=s1.length();i++){
    for(int j=1;j<=s2.length();j++){
    if(s1.charAt(i-1)==s2.charAt(j-1)){
    ar[i][j]=ar[i-1][j-1];
    }else{
    ar[i][j]=Math.min(ar[i-1][j-1],Math.min(ar[i-1][j],ar[i][j-1]))+1;
    }
    }
    }
   
    return ar[s1.length()][s2.length()];
   
    }
   
}

Input:-

1
FOOD
MONEY 

Output:-

4

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------