目录
题目
应用 1:最长公共子串
题目
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子串的长度。如果不存在 公共子串 ,返回 0 。
示例 1:
输入:text1 = "abcbcde", text2 = "bbcbce"
输出:4
解释:最长公共子串是 "bcbc" ,它的长度为 4 。
解题思路
我们使用动态规划求解,设 \(dp[i][j]\) 表示字符串 \(text_1\) 的前 \(i\) 个字符,与字符串 \(text_2\) 的前 \(j\) 个字符的最长公共子串,即子串 \(text_1[:i-1]\) 与子串 \(text_2[:j-1]\) 的最长公共子串的长度。
这里,我们假设字符串 \(text_1\) 和字符串 \(text_2\) 的长度分别为 \(m\)、\(n\)。
边界条件
显然,当其中一个数组长度为零时,它们的公共前缀为零,因此,初始条件为:
\[\begin{aligned} dp[i][0] &= 0, \quad 0 \le i \le m\\ dp[0][j] &= 0, \quad 0 \le j \le n \end{aligned} \]状态转移
当两个字符串的长度大于 \(1\) 时,对于子串 \(text_1[:i-1]\) 与子串 \(text_2[:j-1]\) 的最后一个字符 \(text_1[i-1]\)、\(text_2[j-1]\) :
-
如果 \(text_1[i - 1] = text_2[j - 1]\),那么,当前状态可以由前一个状态转移得到,此时,公共子串的长度较上一个状态增加了一个字符的长度;
-
如果 \(text_1[i - 1] \ne text_2[j - 1]\),那么,以字符 \(text_1[i-1]\) 和字符 \(text_2[j-1]\) 结尾的子串没有公共前缀,此时,它们的最长公共子串长度为零。
因此,状态转移方程为:
\[dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1, &text_1[i-1] = text_2[j-1]\\ 0, & text_1[i - 1] \ne text_2[j - 1] \end{cases} \]代码实现
class Solution {
public int LongestCommonSubStr(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
int result = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
result = Math.max(result, dp[i][j]);
}
}
return result;
}
}
应用 2:Leetcode 718. 最长重复子数组
题目
解题思路
代码实现
给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1:
输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。
解题思路
方法一:动态规划
注意,这里的子数组是连续的子数组。
这里,我们假设数组 \(num1\) 和数组 \(num2\) 的长度分别为 \(m\)、\(n\)。
同时,假设 \(dp[i][j]\) 表示子数组 \(num1[0 \cdots i - 1]\) 和子数组 \(num2[0 \cdots j - 1]\) 的最长公共前缀。
初始条件
显然,当其中一个数组长度为零时,它们的公共前缀为零,因此,初始条件为:
\[\begin{aligned} dp[i][0] &= 0, \quad 0 \le i \le m\\ dp[0][j] &= 0, \quad 0 \le j \le n \end{aligned} \]状态转移
当字符长度大于零时,我们可以考虑枚举其中一个数组的前缀,这里假设枚举前缀 \(num1[0 \cdots i - 1]\),那么,此时,我们只需要枚举另一个数组的前缀即可,只要某一个字符不相等,下一个位置的前缀就要从 \(0\) 开始计算。
即对于子数组 \(num1[0 \cdots i - 1]\) 和子数组 \(num2[0 \cdots j - 1]\):
-
如果数字 \(num1[i - 1]\) 与数字 \(num2[j - 1]\)相等,那么,它们显然可以构成更长的数组前缀;
-
如果它们不相等,那么,它们的公共前缀就为零。
因此,状态转移方程为:
\[dp[i][j]= \begin{cases} dp[i - 1][j - 1] + 1, &num1[i - 1] = num2[j - 1]\\ 0, & num1[i - 1] \ne num2[j - 1] \end{cases} \]复杂度
-
时间复杂度: \(O(n \times m)\)
-
空间复杂度: \(O(n \times m)\)
方法二:滑动窗口
我们考虑使用滑动窗口的思路求解,我们以其中一个数组为基准,枚举它的起始位置,并求解它与另一个数组的最长公共前缀。
复杂度
-
时间复杂度: \(O((m + n) \times min(m, n))\)
-
空间复杂度: \(O(1)\)
代码实现
- 方法一
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
int result = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
result = Math.max(result, dp[i][j]);
}
}
return result;
}
}
- 方法二
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int n = nums1.length, m = nums2.length;
int result = 0;
for (int i = 0; i < n; i++) {
int length = Math.min(m, n - i);
int maxLength = getMaxLength(nums1, nums2, i, 0, length);
result = Math.max(result, maxLength);
}
for (int i = 0; i < m; i++) {
int length = Math.min(n, m - i);
int maxLength = getMaxLength(nums1, nums2, 0, i, length);
result = Math.max(result, maxLength);
}
return result;
}
private int getMaxLength(int[] a, int[] b, int i, int j, int length) {
int result = 0, count = 0;
for (int k = 0; k < length; k++) {
if (a[i + k] == b[j + k]) {
count++;
} else {
count = 0;
}
result = Math.max(result, count);
}
return result;
}
}
标签:子串,int,text,数组,公共,最长,dp From: https://www.cnblogs.com/larry1024/p/18007566