leetcode EditDistance
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class EditDistance {
    /*
    Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

    You have the following 3 operations permitted on a word:

    Insert a character
    Delete a character
    Replace a character

    "zoologicoarchaeologist"
    "zoo  g        eologist"
     */
    public static void main(String[] args){
        System.out.print(editDistance("zoo", "zo"));

    }
    public static int editDistance(String a, String b){
        int m = a.length();
        int n = b.length();

        int[][] matrix = new int[m+1][n+1];
        for (int i=0; i<=n; i++){
            matrix[0][i] = i;
        }
        for (int i=0; i<=m; i++){
            matrix[i][0] = i;
        }
        for (int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if (a.charAt(i-1) == b.charAt(j-1)){
                    matrix[i][j] = Math.min(Math.min(matrix[i-1][j-1], matrix[i][j-1]+1), matrix[i-1][j]+1);
                }
                else {
                    matrix[i][j] = Math.min(Math.min(matrix[i-1][j-1], matrix[i][j-1]), matrix[i-1][j]) + 1;
                }
            }
        }
        for (int i=0; i<=m; i++){
            for (int j=0; j<=n; j++){
                System.out.print(matrix[i][j] + "\t");
            }
            System.out.println();
        }
        return matrix[m][n];

    }
}