代码随想录训练营第56天|583.两个字符串的删除操作，72.编辑距离

583.两个字符串的删除操作

文章

代码随想录|0583.两个字符串的删除操作

思路

如果不按照编辑距离考虑的话，只需要求最长相同子序列的长度l，则word1.length()+word2.length-2*l即为所求

代码

class Solution {
    public int minDistance(String word1, String word2) {
        int i, j, m, n;
        m = word1.length();
        n = word2.length();
        int[][] dp = new int[m][n];
        for (i = 0; i < m; ++i) {
            for (j = 0; j < n; ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? 1 :0;
                } else if (i == 0) {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? 1 : dp[i][j - 1];
                } else if (j == 0) {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? 1 : dp[i - 1][j];
                } else {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? (dp[i - 1][j - 1] + 1) : Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return m + n - 2 * dp[m - 1][n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

72.编辑距离

文章

代码随想录|0072.编辑距离

思路

dp[i][j]表示Word1从0到i的部分与word2从0到j部分的编辑距离
显然如果word1[0]==word2[0]则有dp[0][0]=0否则为1
当比较到word1[i]和word2[j]时，如果相等则dp[i][j]=dp[i-1][j-1]
否则就是dp[i][j]=Min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])

代码

class Solution {
    public int minDistance(String word1, String word2) {
        int i, j, m, n;
        m = word1.length();
        n = word2.length();
        if (m == 0 || n == 0) {
            return Math.max(m, n);
        }
        int[][] dp = new int[m][n];
        for (i = 0; i < m; ++i) {
            for (j = 0; j < n; ++j) {
                if (i == 0 && j == 0) {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? 0 : 1;
                } else if (i == 0) {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? j : dp[i][j - 1] + 1;
                } else if (j == 0) {
                    dp[i][j] = word1.charAt(i) == word2.charAt(j) ? i : dp[i - 1][j] + 1;
                } else {
                    if (word1.charAt(i) == word2.charAt(j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                    }
                }
            }
        }
        return dp[m -1][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

总结

编辑距离似乎前两天刚刷过