牛客热题：最长公共子串
📟作者主页：慢热的陕西人
🌴专栏链接：力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
文章目录
- 牛客热题：最长公共子串
- 题目链接
- 方法一：动态规划
- 思路
- 代码
- 复杂度
- 方法二：dp数组的空间优化
- 思路
- 代码
- 复杂度
牛客热题：最长公共子串
题目链接
最长公共子串_牛客题霸_牛客网 (nowcoder.com)
方法一：动态规划
思路
代码
string LCS(string str1, string str2)
{
int LastIndex = 0;
int MaxLength = 0;
int len1 = str1.size();
int len2 = str2.size();
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for(int i = 1; i <= len1; ++i)
for(int j = 1; j <= len2; ++j)
{
if(str1[i - 1] == str2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if(dp[i][j] > MaxLength)
{
MaxLength = dp[i][j];
LastIndex = i;
}
}
return str1.substr(LastIndex - MaxLength, MaxLength);
}
复杂度
时间复杂度：
O
(
m
∗
n
)
O(m * n)
O(m∗n)相当于遍历了一遍二维数组
O
(
m
∗
n
)
O(m * n)
O(m∗n), 其中
substr的时间复杂度应该是O(N);空间复杂度：
O
(
m
∗
n
)
O(m * n)
O(m∗n)使用了一个二维的dp数组
方法二：dp数组的空间优化
思路
优化思路：
首先我们发现遍历dp数组的时候，只会利用到dp数组的左上位置的信息。所以我们可以将dp数组缩减为一维数组的形式，重复利用这部分空间。
但是由于
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
−
1
]
+
1
dp[i][j] = dp[i – 1][j – 1] + 1
dp[i][j]=dp[i−1][j−1]+1的做法之前的j的正向遍历悠久导致
d
p
[
j
−
1
]
dp[j – 1]
dp[j−1]其中的数据并不是我们想要的。所以我们进行了反向填写的操作。
代码
string LCS(string str1, string str2)
{
int LastIndex = 0;
int MaxLength = 0;
int len1 = str1.size();
int len2 = str2.size();
vector<int> dp(len2 + 1);
for(int i = 1; i <= len1; ++i)
for(int j = len2; j >= 1; --j)
{
if(str1[i - 1] == str2[j - 1])
{
dp[j] = dp[j - 1] + 1;
if(dp[j] > MaxLength)
{
MaxLength = dp[j];
LastIndex = i;
}
}
else
{
dp[j] = 0;
}
}
return str1.substr(LastIndex - MaxLength, MaxLength);
}
复杂度
时间复杂度：
O
(
m
∗
n
)
O(m * n)
O(m∗n)相当于遍历了一遍二维数组
O
(
m
∗
n
)
O(m * n)
O(m∗n), 其中
substr的时间复杂度应该是O(N);空间复杂度:
O
(
n
)
O(n)
O(n), 我们优化了空间，使用了长度等于第二个字符串的dp数组
