leetcode 583. Delete Operation for Two Strings | 583. 两个字符串的删除操作（最长公共子序列，DP）

客官°小女子只卖身不卖艺 2022-08-28 08:56 164阅读 0赞

## 题目 ##

[https://leetcode.com/problems/delete-operation-for-two-strings/][https_leetcode.com_problems_delete-operation-for-two-strings]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

本题实质上是个最长公共子序列问题，又是经典的 递归->傻缓存->dp 得到最长公共子序列的长度 common，最后，三种方法都统一返回 `s1.length() + s2.length() - 2 * common;` 即可。

class Solution { 
        // 实质上是个最长公共子序列问题
        public int minDistance(String s1, String s2) { 
            // Approach 1: Recursive, Brute Force
           // int common = process1(s1, s2, 0, 0);
    
            // Approach 2: Recursion with Memoization
           // int[][] dp = new int[s1.length() + 1][s2.length() + 1];
           // for (int i = 0; i < s1.length(); i++) { 
           // for (int j = 0; j < s2.length(); j++) { // 除了最后一行最后一列以外，全填初始值-1
           // dp[i][j] = -1;
           // }
           // }
           // int common = process2(s1, s2, 0, 0, dp);
    
            // Approach 3: Dynamic Programming
            int[][] dp = new int[s1.length() + 1][s2.length() + 1];
            for (int i = 0; i < s1.length(); i++) { 
                for (int j = 0; j < s2.length(); j++) { 
                    dp[i][j] = -1;
                }
            }
            for (int p1 = s1.length() - 1; p1 >= 0; p1--) { 
                for (int p2 = s2.length() - 1; p2 >= 0; p2--) { 
                    if (s1.charAt(p1) == s2.charAt(p2)) dp[p1][p2] = 1 + dp[p1 + 1][p2 + 1];
                    else dp[p1][p2] = Math.max(dp[p1][p2 + 1], dp[p1 + 1][p2]);
                }
            }
            int common = dp[0][0];
            
            return s1.length() + s2.length() - 2 * common;
        }
    
    // public int process1(String s1, String s2, int p1, int p2) { 
    // if (p1 == s1.length() || p2 == s2.length()) return 0;
    // int res = 0;
    // if (s1.charAt(p1) == s2.charAt(p2)) res = 1 + process1(s1, s2, p1 + 1, p2 + 1);
    // else res = Math.max(process1(s1, s2, p1 + 1, p2), process1(s1, s2, p1, p2 + 1));
    // return res;
    // }
    
    // public int process2(String s1, String s2, int p1, int p2, int[][] dp) { 
    // if (dp[p1][p2] >= 0) return dp[p1][p2];
    // int res = 0;
    // if (s1.charAt(p1) == s2.charAt(p2)) res = 1 + process2(s1, s2, p1 + 1, p2 + 1, dp);
    // else res = Math.max(process2(s1, s2, p1 + 1, p2, dp), process2(s1, s2, p1, p2 + 1, dp));
    // dp[p1][p2] = res;
    // return dp[p1][p2];
    // }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_delete-operation-for-two-strings]: https://leetcode.com/problems/delete-operation-for-two-strings/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/491d5e07772144b6a51a07474bd474d0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/4002450e576e416abfec2b31787f5c76.png