字符串的动态规划系列

linwt · linwt · commit 95d6b1443236 · 2022-03-21T23:20:03.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -75,12 +75,16 @@
 538. 把二叉搜索树转换为累加树
 543. 二叉树的直径
 560. 和为 K 的子数组
+583. 两个字符串的删除操作
 589. N叉树的前序遍历
 617. 合并二叉树
 674. 最长连续递增序列
 695. 岛屿的最大面积
 698. 划分为k个相等的子集
+712. 两个字符串的最小ASCII删除和
 714. 买卖股票的最佳时机含手续费
+718. 最长重复子数组
 1020. 飞地的数量
+1143. 最长公共子序列
 1254. 统计封闭岛屿的数目
 1905. 统计子岛屿
diff --git a/leetcode_Java/Solution0583.java b/leetcode_Java/Solution0583.java
@@ -0,0 +1,25 @@
+// 583. 两个字符串的删除操作
+
+
+class Solution {
+    public int minDistance(String word1, String word2) {
+        int n = word1.length(), m = word2.length();
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 0; i <= n; i++) {
+            dp[i][0] = i;
+        }
+        for (int j = 0; j <= m; j++) {
+            dp[0][j] = j;
+        }
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
+                    dp[i][j] = dp[i - 1][j - 1];
+                } else {
+                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
+                }
+            }
+        }
+        return dp[n][m];
+    }
+}
diff --git a/leetcode_Java/Solution0712.java b/leetcode_Java/Solution0712.java
@@ -0,0 +1,25 @@
+// 712. 两个字符串的最小ASCII删除和
+
+
+class Solution {
+    public int minimumDeleteSum(String s1, String s2) {
+        int n = s1.length(), m = s2.length();
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 1; i <= n; i++) {
+            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
+        }
+        for (int j = 1; j <= m; j++) {
+            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
+        }
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
+                    dp[i][j] = dp[i - 1][j - 1];
+                } else {
+                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
+                }
+            }
+        }
+        return dp[n][m];
+    }
+}
diff --git a/leetcode_Java/Solution0718.java b/leetcode_Java/Solution0718.java
@@ -0,0 +1,42 @@
+// 718. 最长重复子数组
+
+
+class Solution {
+    public int findLength(int[] nums1, int[] nums2) {
+        int n = nums1.length, m = nums2.length;
+        int res = 0;
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (nums1[i - 1] == nums2[j - 1]) {
+                    dp[i][j] = dp[i - 1][j - 1] + 1;
+                    res = Math.max(res, dp[i][j]);
+                } else {
+                    dp[i][j] = 0;
+                }
+            }
+        }
+        return res;
+    }
+}
+
+
+/*
+如果是求“最长重复子序列”，即不要求连续，则解法如下。解法与“1143.最长公共子序列”相同
+ */
+class Solution {
+    public int findLength(int[] nums1, int[] nums2) {
+        int n = nums1.length, m = nums2.length;
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (nums1[i - 1] == nums2[j - 1]) {
+                    dp[i][j] = dp[i - 1][j - 1] + 1;
+                } else {
+                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
+                }
+            }
+        }
+        return dp[n][m];
+    }
+}
diff --git a/leetcode_Java/Solution1143.java b/leetcode_Java/Solution1143.java
@@ -0,0 +1,19 @@
+// 1143. 最长公共子序列
+
+
+class Solution {
+    public int longestCommonSubsequence(String text1, String text2) {
+        int n = text1.length(), m = text2.length();
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
+                    dp[i][j] = dp[i - 1][j - 1] + 1;
+                } else {
+                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
+                }
+            }
+        }
+        return dp[n][m];
+    }
+}
