두 개의 문자열 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) 크기의 2D 배열 dp 하나 정의
-
i :=n, j :=m
-
s1 :=s1 앞에 빈 문자열 연결
-
s2 :=s2 앞에 빈 문자열 연결
-
initialize 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는 0이 아니고 j는 0이 아님) −
-
dp[i, j]가 dp[i - 1, j]와 같으면 -
-
(i를 1 감소)
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
dp[i, j]가 dp[i, j - 1]과 같으면 -
-
(j를 1만큼 감소)
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
렛 :=렛 + s1[i]
-
(i를 1 감소)
-
(j를 1만큼 감소)
-
-
ret 배열 반전
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
s3 :=getLCS(str1, str2)
-
ret :=빈 문자열, i :=0, j :=0, k :=0
-
k
-
i
-
렛 :=렛 + str1[i]
-
(i를 1씩 증가)
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
j
-
렛 :=렛 + str2[j]
-
(j를 1씩 증가)
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
렛 :=렛 + s3[k]
-
(i, j, k를 1씩 증가)
-
-
내가
-
렛 :=렛 + str1[i]
-
(i를 1씩 증가)
-
-
j
-
렛 :=렛 + str2[j]
-
(j를 1씩 증가)
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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