edit-distance-CSES.java

edit-distance-CSES.java

import java.io.*;       

public class editDistance {


static void main(String[] args) {

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ;
       BufferedReader s = br.readLine();       
       BufferedReader d = br.readLine();

       int n = s.length();
       int m = d.length();

       int[][] dp = new int[n+1][m+1];

        //completam linia cu inserari
       for(int j = 0; j <= m; ++j) {
           dp[0][j] = j;
       }

       //completam coloana cu stergeri
       for(int i = 0; i <= n; ++i) {
           dp[i][0] = i;
       }

          for(int i = 1; i <= n; ++i) {

                 for(int j = 1; j <= m; ++j) {


                       char ch1 = s.charAt(i-1);
                       char ch2 = s.charAt(j-1);

                       if(ch1 == ch2) {

                         dp[i][j] = dp[i-1][j-1];

                       } else {

                         int del = 1 + dp[i-1][j];
                         int rep = 1 + dp[i-1][j-1];
                         int ins = 1 + dp[i][j-1];

                         dp[i][j] = Math.min(del, Math.min(rep, ins));

                       }                    
                 }
          }

          System.out.println(dp[n][m]);
}

}