字符串的动态规划系列

linwt · linwt · commit b75f2327b2bf · 2022-03-22T22:59:16.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -32,6 +32,7 @@
 104. 二叉树的最大深度
 105. 从前序与中序遍历序列构造二叉树
 114. 二叉树展开为链表
+115. 不同的子序列
 121. 买卖股票的最佳时机
 122. 买卖股票的最佳时机 II
 123. 买卖股票的最佳时机 III
@@ -61,6 +62,7 @@
 309. 最佳买卖股票时机含冷冻期
 322. 零钱兑换
 338. 比特位计数
+392. 判断子序列
 406. 根据身高重建队列
 416. 分割等和子集
 437. 路径总和
@@ -71,20 +73,23 @@
 491. 递增子序列
 494. 目标和
 509. 斐波那契数
+516. 最长回文子序列
 518. 零钱兑换 II
 538. 把二叉搜索树转换为累加树
 543. 二叉树的直径
 560. 和为 K 的子数组
 583. 两个字符串的删除操作
 589. N叉树的前序遍历
 617. 合并二叉树
+647. 回文子串
 674. 最长连续递增序列
 695. 岛屿的最大面积
 698. 划分为k个相等的子集
 712. 两个字符串的最小ASCII删除和
 714. 买卖股票的最佳时机含手续费
 718. 最长重复子数组
 1020. 飞地的数量
+1035. 不相交的线
 1143. 最长公共子序列
 1254. 统计封闭岛屿的数目
 1905. 统计子岛屿
diff --git a/leetcode_Java/Solution0115.java b/leetcode_Java/Solution0115.java
@@ -0,0 +1,22 @@
+// 115. 不同的子序列
+
+
+class Solution {
+    public int numDistinct(String s, String t) {
+        int n = s.length(), m = t.length();
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 0; i <= n; i++) {
+            dp[i][0] = 1;
+        }
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (s.charAt(i - 1) == t.charAt(j - 1)) {
+                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
+                } else {
+                    dp[i][j] = dp[i - 1][j];
+                }
+            }
+        }
+        return dp[n][m];
+    }
+}
diff --git a/leetcode_Java/Solution0392.java b/leetcode_Java/Solution0392.java
@@ -0,0 +1,41 @@
+// 392. 判断子序列
+
+
+/*
+实际就是“1143.最长公共子序列”
+ */
+class Solution {
+    public boolean isSubsequence(String s, String t) {
+        int n = s.length(), m = t.length();
+        int[][] dp = new int[n + 1][m + 1];
+        for (int i = 1; i <= n; i++) {
+            for (int j = 1; j <= m; j++) {
+                if (s.charAt(i - 1) == t.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] == n ? true : false;
+    }
+}
+
+
+/*
+双指针：两个指针分别指向字符串s和t，当两个指针指向的字符相等时 i指针才向右移动一步，j指针每次都向右移动一步，只要其中一个字符串遍历完就结束，
+      最后判断i指针是否到了末尾，是则表示s是t的子序列，否则不是
+ */
+class Solution {
+    public boolean isSubsequence(String s, String t) {
+        int n = s.length(), m = t.length();
+        int i = 0, j = 0;
+        while (i < n && j < m) {
+            if (s.charAt(i) == t.charAt(j)) {
+                i++;
+            }
+            j++;
+        }
+        return i == n ? true : false;
+    }
+}
diff --git a/leetcode_Java/Solution0516.java b/leetcode_Java/Solution0516.java
@@ -0,0 +1,27 @@
+// 516. 最长回文子序列
+
+
+class Solution {
+    public int longestPalindromeSubseq(String s) {
+        int n = s.length(), res = 1;
+        int[][] dp = new int[n][n];
+        for (int i = 0; i < n; i++) {
+            dp[i][i] = 1;
+        }
+        for (int r = 1; r < n; r++) {
+            for (int l = r - 1; l >= 0; l--) {
+                if (s.charAt(l) == s.charAt(r)) {
+                    if (r - l == 1) {
+                        dp[l][r] = 2;
+                    } else {
+                        dp[l][r] = dp[l + 1][r - 1] + 2;
+                    }
+                } else {
+                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
+                }
+                res = Math.max(res, dp[l][r]);
+            }
+        }
+        return res;
+    }
+}
diff --git a/leetcode_Java/Solution0647.java b/leetcode_Java/Solution0647.java
@@ -0,0 +1,25 @@
+// 647. 回文子串
+
+
+/*
+与“5.最长回文子串”相似
+ */
+class Solution {
+    public int countSubstrings(String s) {
+        int n = s.length();
+        int res = n;
+        boolean[][] dp = new boolean[n][n];
+        for (int i = 0; i < n; i++) {
+            dp[i][i] = true;
+        }
+        for (int r = 1; r < n; r++) {
+            for (int l = 0; l < r; l++) {
+                if (s.charAt(l) == s.charAt(r) && (r - l < 3 || dp[l + 1][r - 1])) {
+                    dp[l][r] = true;
+                    res++;
+                }
+            }
+        }
+        return res;
+    }
+}
diff --git a/leetcode_Java/Solution1035.java b/leetcode_Java/Solution1035.java
@@ -0,0 +1,22 @@
+// 1035. 不相交的线
+
+
+/*
+实际就是“1143.最长公共子序列”
+ */
+class Solution {
+    public int maxUncrossedLines(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];
+    }
+}
