BM65. 最长公共子序列(二)
描述
示例1
输入:
"1A2C3D4B56","B1D23A456A"
输出:
"123456"
示例2
输入:
"abc","def"
输出:
"-1"
示例3
输入:
"abc","abc"
输出:
"abc"
示例4
输入:
"ab",""
输出:
"-1"
C++ 解法, 执行用时: 4ms, 内存消耗: 524KB, 提交时间: 2022-06-17
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
/*int n = s1.size();
int m = s2.size();
string dp[n+1][m+1];
for(int i=0;i<=n;i++) dp[i][0]="";
for(int j=0;j<=m;j++) dp[0][j]="";
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+s1[i-1];
else{
dp[i][j]=dp[i-1][j].size()>dp[i][j-1].size()?dp[i-1][j]:dp[i][j-1];
}
}
}
return dp[s1.size()][s2.size()]==""?"-1":dp[s1.size()][s2.size()];
}*/
if(s1.empty()||s2.empty()) return "-1";
vector<vector<int> > hashTable(128,vector<int>());
vector<int> A;
for(int i=0;i<s1.size();i++)
hashTable[s1[i]].push_back(i);
for(int i=0;i<s2.size();i++)
for(int j=hashTable[s2[i]].size()-1;j>=0;j--)
A.push_back(hashTable[s2[i]][j]);
int N = A.size(), topSize=1;
if(!N) return "-1";
vector<int> top(N,0), topIndexs(N,0), pre(N,0);
top[0]=A[0];
for(int i=0;i<N;i++)
{
if(A[i]>top[topSize-1])
{
pre[i] = topIndexs[topSize-1];
top[topSize] = A[i];
topIndexs[topSize++] = i;
}
else
{
int pos = lower_bound(top.begin(),top.begin()+topSize,A[i])-top.begin();
if(pos) pre[i] = topIndexs[pos-1];
top[pos]=A[i];
topIndexs[pos]=i;
}
}
int endIndex = topIndexs[topSize-1];
string seq(topSize,0);
for(int i = topSize-1,s=endIndex;i>=0;i--,s=pre[s])
seq[i]=s1[A[s]];
return seq;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 524KB, 提交时间: 2022-05-20
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
if(s1.empty()||s2.empty()) return "-1";
vector<vector<int> > hashTable(128,vector<int>());
vector<int> A;
for(int i=0;i<s1.size();i++)
hashTable[s1[i]].push_back(i);
for(int i=0;i<s2.size();i++)
for(int j=hashTable[s2[i]].size()-1;j>=0;j--)
A.push_back(hashTable[s2[i]][j]);
int N = A.size(), topSize=1;
if(!N) return "-1";
vector<int> top(N,0), topIndexs(N,0), pre(N,0);
top[0]=A[0];
for(int i=0;i<N;i++)
{
if(A[i]>top[topSize-1])
{
pre[i] = topIndexs[topSize-1];
top[topSize] = A[i];
topIndexs[topSize++] = i;
}
else
{
int pos = lower_bound(top.begin(),top.begin()+topSize,A[i])-top.begin();
if(pos) pre[i] = topIndexs[pos-1];
top[pos]=A[i];
topIndexs[pos]=i;
}
}
int endIndex = topIndexs[topSize-1];
string seq(topSize,0);
for(int i = topSize-1,s=endIndex;i>=0;i--,s=pre[s])
seq[i]=s1[A[s]];
return seq;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 532KB, 提交时间: 2022-06-11
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
if(s1.empty()||s2.empty()) return "-1";
vector<vector<int> > hashTable(128,vector<int>());
vector<int> A;
for(int i=0;i<s1.size();i++)
hashTable[s1[i]].push_back(i);
for(int i=0;i<s2.size();i++)
for(int j=hashTable[s2[i]].size()-1;j>=0;j--)
A.push_back(hashTable[s2[i]][j]);
int N = A.size(), topSize=1;
if(!N) return "-1";
vector<int> top(N,0), topIndexs(N,0), pre(N,0);
top[0]=A[0];
for(int i=0;i<N;i++)
{
if(A[i]>top[topSize-1])
{
pre[i] = topIndexs[topSize-1];
top[topSize] = A[i];
topIndexs[topSize++] = i;
}
else
{
int pos = lower_bound(top.begin(),top.begin()+topSize,A[i])-top.begin();
if(pos) pre[i] = topIndexs[pos-1];
top[pos]=A[i];
topIndexs[pos]=i;
}
}
int endIndex = topIndexs[topSize-1];
string seq(topSize,0);
for(int i = topSize-1,s=endIndex;i>=0;i--,s=pre[s])
seq[i]=s1[A[s]];
return seq;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 556KB, 提交时间: 2022-07-09
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
if(s1.empty()||s2.empty()) return "-1";
vector<vector<int>> hashTable(128,vector<int>());
vector<int> A;
for(int i=0; i<s1.size(); i++)
hashTable[s1[i]].push_back(i);
for(int i=0; i<s2.size(); i++)
for(int j=hashTable[s2[i]].size()-1; j>=0; j--)
A.push_back(hashTable[s2[i]][j]);
int N = A.size(), topSize=1;
if(!N) return "-1";
vector<int> top(N,0), topIndexs(N,0), pre(N,0);
top[0] = A[0];
for(int i=0; i<N; i++)
{
if(A[i]>top[topSize-1])
{
pre[i] = topIndexs[topSize-1];
top[topSize] = A[i];
topIndexs[topSize++] = i;
}
else
{
int pos = lower_bound(top.begin(), top.begin()+topSize, A[i])-top.begin();
if (pos) pre[i] = topIndexs[pos-1];
top[pos]=A[i];
topIndexs[pos]=i;
}
}
int endIndex = topIndexs[topSize-1];
string seq(topSize,0);
for(int i= topSize-1, s=endIndex; i >= 0; i--,s=pre[s])
seq[i] = s1[A[s]];
return seq;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 512KB, 提交时间: 2022-05-06
class Solution {
public:
/**
* longest common subsequence
* @param s1 string字符串 the string
* @param s2 string字符串 the string
* @return string字符串
*/
string LCS(string s1, string s2) {
// write code here
if (s1.empty() || s2.empty())
return string("-1");
vector<vector<int>> hashTable(128, vector<int>());
vector<int> A;
for (int i = 0; i < s1.size(); i++) {
hashTable[s1[i]].push_back(i);
}
for (int i = 0; i < s2.size(); i++) {
for (int j = hashTable[s2[i]].size() - 1; j >= 0; j--) {
A.push_back(hashTable[s2[i]][j]);
}
}
int N = A.size(), topSize = 1;
if (N == 0)
return "-1";
vector<int> top(N, 0), topIndexes(N, 0), pre(N, 0);
top[0] = A[0];
for (int i = 1; i < N; i++) {
if (A[i] > top[topSize - 1]) {
pre[i] = topIndexes[topSize - 1];
top[topSize] = A[i];
topIndexes[topSize++] = i;
} else {
int pos = lower_bound(top.begin(), top.begin() + topSize, A[i]) - top.begin();
if (pos)
pre[i] = topIndexes[pos - 1];
top[pos] = A[i];
topIndexes[pos] = i;
}
}
int endIndex = topIndexes[topSize - 1];
string seq(topSize, 0);
for (int i = topSize - 1, s = endIndex; i >= 0; i--, s = pre[s]) {
seq[i] = s1[A[s]];
}
return seq;
}
};