LeetCode/Edit Distance at master · Gforky/LeetCode · 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 int minDistance(String word1, String word2) {
    if(word2.length() == 0)
        return word1.length();

    int[] distance = new int[word2.length() + 1];
    for(int k = 1; k <= word2.length(); k++)
        distance[k] = k;

    for(int i = 0; i < word1.length(); i++){
        int []curDistance = new int[word2.length() + 1];
        curDistance[0] = i + 1;
        for(int j = 0; j < word2.length(); j++){
            int substitute = distance[j] + (word1.charAt(i) == word2.charAt(j)? 0 : 1);
            int delete = distance[j + 1] + 1;
            int insert = curDistance[j] + 1;
            curDistance[j + 1] = Math.min(substitute, Math.min(delete, insert));
        }
        distance = curDistance;
    }

    return distance[word2.length()];
}
}