Coding-ninjas-data-st.-through-java/DP-2: Edit Distance at master · NOOBE666/Coding-ninjas-data-st.-through-java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public static int editDistance(String s1, String s2){
        if(s1.length()==0 && s2.length()==0)
            return 0;
        if(s2.length()==0)
            return s1.length();
        if(s1.length()==0)
            return s2.length();

        if(s1.charAt(0)==s2.charAt(0))
            return editDistance(s1.substring(1),s2.substring(1));
        else{
            //insert
            int op1=editDistance(s1,s2.substring(1));
            //delete
             int op2=editDistance(s1.substring(1),s2);
            //substitute
             int op3=editDistance(s1.substring(1),s2.substring(1));
            return 1+Math.min(op1,Math.min(op2,op3));

        }
        }
}