資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最短公共超序列
假設我們有兩個字串 str1 和 str2，我們需要找到一個最短的字串，它同時包含 str1 和 str2 作為子序列。可能存在多個結果，因此我們只需要返回其中一個。
如你所知，如果從字串 T 中刪除一些字元（可能為 0 個，並且這些字元可以從 T 中的任意位置選擇）得到字串 S，則稱字串 S 為字串 T 的子序列。
因此，如果輸入為 "acab" 和 "bac"，則輸出將為 "bacab"，這是因為這兩個給定的字串都是其子序列。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 getLCS()，它將接收 s1 和 s2 作為輸入，
ret := 空字串
n := s1 的大小，m := s2 的大小
定義一個大小為 (n + 1) x (m + 1) 的二維陣列 dp
i := n，j := m
s1 := 在 s1 前面連線空字串
s2 := 在 s2 前面連線空字串
對於初始化 i := 1，當 i <= n 時，更新（i 增加 1），執行以下操作：
對於初始化 j := 1，當 j <= m 時，更新（j 增加 1），執行以下操作：
如果 s1[i] 與 s2[j] 相同，則：
dp[i, j] := 1 + dp[i - 1, j - 1]
否則
dp[i, j] := dp[i - 1, j] 和 dp[i, j - 1] 的最大值
當 (i 非零且 j 非零) 時，執行以下操作：
如果 dp[i, j] 與 dp[i - 1, j] 相同，則：
(i 減 1)
忽略以下部分，跳到下一個迭代
如果 dp[i, j] 與 dp[i, j - 1] 相同，則：
(j 減 1)
忽略以下部分，跳到下一個迭代
ret := ret + s1[i]
(i 減 1)
(j 減 1)
反轉陣列 ret
返回 ret
從主方法執行以下操作：
s3 := getLCS(str1, str2)
ret := 空字串，i := 0，j := 0，k := 0
當 k < s3 的大小 時，執行以下操作：
如果 i < str1 的大小 且 str1[i] 不等於 s3[k]，則：
ret := ret + str1[i]
(i 增加 1)
忽略以下部分，跳到下一個迭代
如果 j < str2 的大小 且 str2[j] 不等於 s3[k]，則：
ret := ret + str2[j]
(j 增加 1)
忽略以下部分，跳到下一個迭代
ret := ret + s3[k]
(i、j、k 增加 1)
當 i < str1 的大小 時，執行以下操作：
ret := ret + str1[i]
(i 增加 1)
當 j < str2 的大小 時，執行以下操作：
ret := ret + str2[j]
(j 增加 1)
返回 ret
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2){
string s3 = getLCS(str1, str2);
string ret = "";
int i = 0;
int j = 0;
int k = 0;
while (k < s3.size()) {
if (i < str1.size() && str1[i] != s3[k]) {
ret += str1[i];
i++;
continue;
}
if (j < str2.size() && str2[j] != s3[k]) {
ret += str2[j];
j++;
continue;
}
ret += s3[k];
k++;
i++;
j++;
}
while (i < str1.size()) {
ret += str1[i];
i++;
}
while (j < str2.size()) {
ret += str2[j];
j++;
}
return ret;
}
string getLCS(string s1, string s2){
string ret = "";
int n = s1.size();
int m = s2.size();
vector<vector<int> > dp(n + 1, vector<int>(m + 1));
int i = n;
int j = m;
s1 = " " + s1;
s2 = " " + s2;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
while (i && j) {
if (dp[i][j] == dp[i - 1][j]) {
i--;
continue;
}
if (dp[i][j] == dp[i][j - 1]) {
j--;
continue;
}
ret += s1[i];
i--;
j--;
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.shortestCommonSupersequence("acab", "bac"));
}輸入
"acab", "bac"
輸出
bacab
139 次檢視
