LeetCode 72. Edit Distance (动归)

港控/mmm° 2024-04-17 23:45 67阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

ok，编辑距离大家都比较熟悉了，画个表格基本ok，我个人的构想起点是左上角，从左到右还是从上到下都代表新增和删除，对角线上代表修改对吧，其实很好理解，i-1， j-1已经计算好了那个位置的最短距离，下一个元素可以选择修改等同。

那么我们的选择无非就是新增、删除、更改中三选一，给出状态转移公式：

dp\[i\]\[j\] = min((dp\[i-1\]\[j\] + 1), (dp\[i\]\[j-1\] + 1), (dp\[i-1\]\[j-1\] + 1)) if(word1\[i-1\] != word2\[j-1\]);  
dp\[i\]\[j\] = min((dp\[i-1\]\[j\] + 1), (dp\[i\]\[j-1\] + 1), (dp\[i-1\]\[j-1\])) if(word1\[i-1\] == word2\[j-1\]);

初始化的就代码里面看吧。

class Solution {
    public:
        int minDistance(string word1, string word2) {
            //赶时间就简写，两个字符串无论如何最开头都认为空串
            //dp[0][0] = 0  空串不用改
            //我们假设我们的起始点是左上角，那么从左往右或者从上往下都可以代表insert或者delete(不理解画个表格)
            //update只在对应位置不同才修改
            //dp[i][j] = min((dp[i-1][j] + 1), (dp[i][j-1] + 1), (dp[i-1][j-1] + 1)) if(word1[i-1] != word2[j-1]);
            //dp[i][j] = min((dp[i-1][j] + 1), (dp[i][j-1] + 1), (dp[i-1][j-1])) if(word1[i-1] == word2[j-1]);
            int n = word1.length();
            int m = word2.length();
            int dp[n+5][m+5];
            //初始
            dp[0][0] = 0;
            dp[1][0] = 1;
            dp[0][1] = 1;
            //空字符对谁都是直接insert所以填
            for(int i = 1; i <= n; i++) dp[i][0] = i;
            for(int j = 1; j <= m; j++) dp[0][j] = j;
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                    if(word1[i-1] == word2[j-1]) dp[i][j] = min((dp[i-1][j] + 1), min((dp[i][j-1] + 1), (dp[i-1][j-1])));
                    else if(word1[i-1] != word2[j-1]) dp[i][j] = min((dp[i-1][j] + 1), min((dp[i][j-1] + 1), (dp[i-1][j-1] + 1)));
                }
            }
            return dp[n][m];
        }
    };

看起来我的代码还挺快的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/ee3bebc757754babb0df308fd470276f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c5cc331ed7e54e44a4fe7ada7b59ce0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/79b789205afa46a49192d635e3f3ac67.png