Leetcode 72：编辑距离

EditDistance.java

package dynamic_program;

// Leetcode 72 编辑距离
// 自底向上的方法

class Solution72 {
    //保存距离
    int[][] dist;
    //保存操作。值 0~3 分别是：0跳过，1插入，2删除，3替换
    int[][] act;
    
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        dist = new int[l1+1][l2+1];
        act = new int[l1+1][l2+1];
        
        for (int i=0; i<=l1; i++) {
            dist[i][0] = i;
            act[i][0] = 2;      //删除
        }

        for (int j=0; j<=l2; j++) {
            dist[0][j] = j;
            act[0][j] = 1;      //插入
        }
        
        for (int i=1; i<=l1; i++) {
            for (int j=1; j<=l2; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)) {
                    dist[i][j] = dist[i-1][j-1];
                    act[i][j] = 0;  //跳过
                }
                else {
                    int add = dist[i][j-1]+1;
                    int rem = dist[i-1][j]+1;
                    int repl = dist[i-1][j-1]+1;
                    
                    if (repl<add && repl<rem) {
                        dist[i][j] = repl;
                        act[i][j] = 3;  //替换
                    }
                    else if (add<rem) {
                        dist[i][j] = add;
                        act[i][j] = 1;  //插入
                    }
                    else {
                        dist[i][j] = rem;
                        act[i][j] = 2;  //删除
                    }
                }
            }
        }
        
        printOperations(act, l1, l2, word1, word2);
        return dist[l1][l2];
    }
    
    public void printOperations(int[][] act,int i,int j, String w1, String w2) {
        System.out.println(w1 + " -> " + w2 + ":");
        while (i!=0 && j!=0) {
            String tmp;
            String s = "";
            switch (act[i][j]) {
            case 0:
                //s = "(跳过)";
                i--;
                j--;
                break;
            case 1:
                tmp = w1.substring(0, i) + w2.charAt(j-1) + w1.substring(i+1);
                s = String.format("%s -> %s (插入 '%c')\n", w1, tmp, w2.charAt(j-1));
                w1 = tmp;
                j--;
                break;
            case 2:
                tmp = w1.substring(0, i-1) + w1.substring(i);
                s = String.format("%s -> %s (删除 '%c')\n", w1, tmp, w1.charAt(i-1));
                w1 = tmp;
                i--;
                break;
            case 3:
                tmp = w1.substring(0, i-1) + w2.charAt(j-1) + w1.substring(i);
                s = String.format("%s -> %s (将 '%c' 替换为 '%c')\n",
                        w1, tmp, w1.charAt(i-1), w2.charAt(j-1));
                w1 = tmp;
                i--;
                j--;
                break;
            }
            System.out.print(s);
        }
    }
}

public class EditDistance {
    public static void main(String[] args) {
        Solution72 s = new Solution72();
        System.out.println(s.minDistance("horse", "ros"));
        System.out.println(s.minDistance("intention", "execution"));
        System.out.println(s.minDistance("consistent", "constraint"));
    }
}