BM66. 最长公共子串
描述
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。
数据范围： 
要求： 空间复杂度)
，时间复杂度
要求： 空间复杂度
示例1
输入:
"1AB2345CD","12345EF"
输出:
"2345"
BM66. 最长公共子串
描述
示例1
输入:
"1AB2345CD","12345EF"
输出:
"2345"
C++ 解法, 执行用时: 4ms, 内存消耗: 524KB, 提交时间: 2022-01-22
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
unordered_map<char, vector<int>> chIndex;
int size1 = str1.size();
int size2 = str2.size();
int maxSize = 0, maxIndex = -1,curIndex,curCount;
int i,j;
for (i = 0; i < size1; i++){
chIndex[str1[i]].emplace_back(i);
}
for (i = 0; i < size2; i++){
if (chIndex.count(str2[i]) == 0) continue;
for (int x: chIndex[str2[i]]){
if ( (size1 - x) < maxSize || (size2 - i) < maxSize)
break;
curIndex = i;
curCount = 0;
j = i;
while (str1[x++] == str2[j++]){
curCount++;
}
if (curCount > maxSize){
maxSize = curCount;
maxIndex = curIndex;
}
}
}
return maxSize>0?str2.substr(maxIndex,maxSize):string();
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 448KB, 提交时间: 2022-03-27
class Solution {
public:
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
// write code here
string LCS(string str1, string str2) {
// write code here
unordered_map<char, vector<int>> chIndex;
int size1 = str1.size();
int size2 = str2.size();
int maxSize = 0, maxIndex = -1,curIndex,curCount;
int i,j;
for (i = 0; i < size1; i++){
chIndex[str1[i]].emplace_back(i);
}
for (i = 0; i < size2; i++){
if (chIndex.count(str2[i]) == 0) continue;
for (int x: chIndex[str2[i]]){
if ( (size1 - x) < maxSize || (size2 - i) < maxSize)
break;
curIndex = i;
curCount = 0;
j = i;
while (str1[x++] == str2[j++]){
curCount++;
}
if (curCount > maxSize){
maxSize = curCount;
maxIndex = curIndex;
}
}
}
return maxSize>0?str2.substr(maxIndex,maxSize):string();
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 512KB, 提交时间: 2022-08-05
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
string LCS(string str1, string str2) {
unordered_map<char, vector<int>> chIndex;
int size1 = str1.size();
int size2 = str2.size();
int maxSize = 0, maxIndex = -1,curIndex,curCount;
int i,j;
for (i = 0; i < size1; i++){
chIndex[str1[i]].emplace_back(i);
}
for (i = 0; i < size2; i++){
if (chIndex.count(str2[i]) == 0) continue;
for (int x: chIndex[str2[i]]){
if ( (size1 - x) < maxSize || (size2 - i) < maxSize)
break;
curIndex = i;
curCount = 0;
j = i;
while (str1[x++] == str2[j++]){
curCount++;
}
if (curCount > maxSize){
maxSize = curCount;
maxIndex = curIndex;
}
}
}
return maxSize>0?str2.substr(maxIndex,maxSize):string();
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 512KB, 提交时间: 2022-03-28
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
unordered_map<char, vector<int>> chIndex;
int size1 = str1.size();
int size2 = str2.size();
int maxSize = 0,maxIndex = -1,curIndex,curCount;
int i,j;
for(int i = 0;i<size1;++i){
chIndex[str1[i]].emplace_back(i);
}
for(int i=0;i<size2;++i){
if(chIndex.count(str2[i]) == 0) continue;
for(int x:chIndex[str2[i]]){
if((size1 -x)<maxSize || (size2 - i)<maxSize) break;
curIndex = i;
curCount=0;
j=i;
while(str1[x++] == str2[j++]){
curCount++;
}
if(curCount > maxSize){
maxSize = curCount;
maxIndex = curIndex;
}
}
}
return maxSize>0?str2.substr(maxIndex,maxSize):string();
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 416KB, 提交时间: 2021-12-09
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
unordered_map<char, vector<int>> chIndex;
int size1 = str1.size();
int size2 = str2.size();
int maxSize = 0, maxIndex = -1,curIndex,curCount;
int i,j;
for (i = 0; i < size1; i++){
chIndex[str1[i]].emplace_back(i);
}
for (i = 0; i < size2; i++){
if (chIndex.count(str2[i]) == 0) continue;
for (int x: chIndex[str2[i]]){
if ( (size1 - x) < maxSize || (size2 - i) < maxSize)
break;
curIndex = i;
curCount = 0;
j = i;
while (str1[x++] == str2[j++]){
curCount++;
}
if (curCount > maxSize){
maxSize = curCount;
maxIndex = curIndex;
}
}
}
return maxSize>0?str2.substr(maxIndex,maxSize):string();
}
};