面试指南——最小编辑代价

题目描述:
给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。
举例:
str1=”abc” str2=”adc” ic=5 dc=3 rc=2,从”abc”编辑到”adc”把b替换成d代价最小,为2;
str1=”abc” str2=”adc” ic=5 dc=3 rc=10,从”abc”编辑到”adc”,先删除b再插入d代价最小,为8;
/*
* 首先生成M+1,N+1的dp矩阵,dp[i][j]代表str1[0…i-1]编辑成str2[0…j-1]的最小代价。
* dp矩阵计算过程如下:
* 1.dp[0][0]=0,表示str1空子串编辑成str2空子串的代价为0;
* 2.矩阵dp第一列dp[0…M-1][0],dp[i][0]表示str1[0…i-1]编辑成空串的最小代价,
* 即将str1[0…i-1]所有的字符删掉的代价,dp[i][0]=dc*i;
* 3.矩阵dp第一行dp[0][0…N-1],dp[0][j]表示将空串编辑成str2[0…j-1]的最小代价,
* 即在空串里插入str2[0…j-1]所有字符的代价,dp[0][j]=ic*j;
* 4.其他位置按照从左到右,从上到下来计算dp值,有以下四种情况:
* a.str1[0…i-1]可以先编辑成str1[0…i-2],也就是删除str1[i-1],然后由str1[0…i-2]编辑成str2[0…j-1],
* dp[i-1][j]表示str1[0…i-2]编辑成str2[0…j-1]的代价,所以,dp[i][j]=dc+dp[i-1][j];
* b.str1[0…i-1]可以先编辑成str2[0…j-2],然后将str2[0…j-2]插入字符str2[j-1],编辑成str2[0…j-1],
* dp[i][j-1]表示将str1[0…i-1]编辑成str2[0…j-2]的代价,所以,dp[i][j]=dp[i][j-1]+ic;
* c.如果str1[i-1]!=str2[j-1],先将str1[0…i-2]编辑成str2[0…j-2],然后将str1[i-1]替换为str2[j-1],
* dp[i-1][j-1]表示将str1[0…i-2]编辑成str2[0…j-2]的代价,所以,dp[i][j]=dp[i-1][j-1]+rc;
* d.如果str1[i-1]==str2[j-1],先将str1[0…i-2]编辑成str2[0…j-2],因为str1[i-1]==str2[j-1],
* dp[i-1][j-1]表示将str1[0…i-2]编辑成str2[0…j-2]的代价,所以,dp[i][j]=dp[i-1][j-1]+rc;
* 以上四种情况,取最小值为dp[i][j]
*
* 通过空间压缩,可以将空间复杂度压缩到N+1
*/

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class 最小编辑代价 {
    public static int minCost1(String str1, String str2, int ic, int dc, int rc) {
        if (str1 == null || str2 == null) {
            return 0;
        }
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        int row = chs1.length + 1;
        int col = chs2.length + 1;
        int[][] dp = new int[row][col];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dc * i;
        }
        for (int j = 1; j < col; j++) {
            dp[0][j] = ic * j;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (chs1[i - 1] == chs2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }
                dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + ic);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + dc);
            }
        }
        return dp[row - 1][col - 1];
    }
    public static int minCost2(String str1, String str2, int ic, int dc, int rc) {
        if (str1 == null || str2 == null) {
            return 0;
        }
        char[] chs1 = str1.toCharArray();
        char[] chs2 = str2.toCharArray();
        char[] longs = chs1.length >= chs2.length ? chs1 : chs2;
        char[] shorts = chs1.length < chs2.length ? chs1 : chs2;
        if (chs1.length < chs2.length) { // str2较长就交换ic和dc的值
            int tmp = ic;
            ic = dc;
            dc = tmp;
        }
        int[] dp = new int[shorts.length + 1];
        for (int i = 1; i <= shorts.length; i++) {
            dp[i] = ic * i;
        }
        for (int i = 1; i <= longs.length; i++) {
            int pre = dp[0]; // pre表示左上角的值
            dp[0] = dc * i;
            for (int j = 1; j <= shorts.length; j++) {
                int tmp = dp[j]; // dp[j]没更新前先保存下来
                if (longs[i - 1] == shorts[j - 1]) {
                    dp[j] = pre;
                } else {
                    dp[j] = pre + rc;
                }
                dp[j] = Math.min(dp[j], dp[j - 1] + ic);
                dp[j] = Math.min(dp[j], tmp + dc);
                pre = tmp; // pre变成dp[j]没更新前的值
            }
        }
        return dp[shorts.length];
    }
    public static void main(String[] args) {
        String str1 = "ab12cd3";
        String str2 = "abcdf";
        System.out.println(minCost1(str1, str2, 5, 3, 2));
        System.out.println(minCost2(str1, str2, 5, 3, 2));

        str1 = "abcdf";
        str2 = "ab12cd3";
        System.out.println(minCost1(str1, str2, 3, 2, 4));
        System.out.println(minCost2(str1, str2, 3, 2, 4));

        str1 = "";
        str2 = "ab12cd3";
        System.out.println(minCost1(str1, str2, 1, 7, 5));
        System.out.println(minCost2(str1, str2, 1, 7, 5));

        str1 = "abcdf";
        str2 = "";
        System.out.println(minCost1(str1, str2, 2, 9, 8));
        System.out.println(minCost2(str1, str2, 2, 9, 8));

    }

}
0 条评论
发表一条评论