题解 | #最长公共子串#
最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。
数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)
要求： 空间复杂度 O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)
示例1
输入：
"1AB2345CD","12345EF"复制
返回值：
"2345"复制
备注：
1 \leq |str_1|, |str_2| \leq 5\,0001≤∣str1∣,∣str2∣≤5000
按之前求最长公共子串长度的方法，先把长度求出来，然后使用res = str1.substr(index-cnt, cnt);来截取
class Solution {
public:
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
string LCS(string str1, string str2) {
// write code here
int n = str1.size();
int m = str2.size();
int cnt = 0;
string res = "";
int index = 0;
// dp[i][j]代表s1的包含第i个元素与s2的包含第j个元素的最长公共子串最大长度
vector<vector<int>>dp(n+1, vector<int>(m+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (str1[i-1] == str2[j-1]) {
if(dp[i-1][j-1] > 0) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 1;
}
}
//cout << "i=" <<i <<", j=" << j << ",dp ="<< dp[i][j] << endl;
if (cnt < dp[i][j]) {
cnt = dp[i][j];
index = i;
}
}
}
cout << cnt;
res = str1.substr(index-cnt, cnt);
return res;
}
};
美的集团公司福利 136人发布