Shortest Common Supersequence
HardStringDynamic Programming
문제 설명
주어진 두 문자열 str1
과 str2
를 모두 부분 문자열(subsequence)로 가지고 있는 최단 문자열을 반환합니다.
- 유효한 문자열이 여러 개 있으면, 그 중 하나를 반환합니다.
- 문자열
t
에서 일부 문자를 삭제하면 문자열s
가 생성되는 경우 문자열s
는 문자열t
의 부분 문자열(subsequence)입니다.
문제 풀이
Longest Common Sequence
str1
과str2
의Longest Common Sequence
을 찾는다.str1
과str2
에서 Longest Common Sequence에 포함되지 않는 문자열을 차례대로 추가한다.- 추가하지 않은 문자열을 뒤에 차례대로 추가한다.
function shortestCommonSupersequence(str1: string, str2: string): string {
const subsequence = longestCommonSubsequence(str1, str2);
let supersequence = '';
let [index1, index2] = [0, 0];
for (const char of subsequence) {
const endIndex1 = str1.indexOf(char, index1);
const endIndex2 = str2.indexOf(char, index2);
supersequence += str1.substring(index1, endIndex1) + str2.substring(index2, endIndex2) + char;
[index1, index2] = [endIndex1 + 1, endIndex2 + 1];
}
return supersequence + str1.substring(index1) + str2.substring(index2);
}
function longestCommonSubsequence(str1: string, str2: string): string {
const [m, n] = [str1.length, str2.length];
const dp = Array.from({ length: m + 1 }, () => new Array<string>(n + 1).fill(''));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + str1[i - 1];
} else if (dp[i - 1][j].length < dp[i][j - 1].length) {
dp[i][j] = dp[i][j - 1];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
복잡도
- :
str1
의 길이, :str2
의 길이, :Longest Common Sequence
의 길이. - 시간 복잡도:
- 공간 복잡도:
더 효율적인 방법
dp
에 현재 subsequence를 저장하는 것이 아니라, subsequence의 길이만을 저장한다.indexOf
과 같은 메서드를 사용하는 것이 아니라, 차례대로 확인한다.
function shortestCommonSupersequence(str1: string, str2: string): string {
const [m, n] = [str1.length, str2.length];
const dp = Array.from({ length: m + 1 }, () => new Array<number>(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
let [i, j] = [m, n];
const supersequence: string[] = [];
while (i > 0 && j > 0) {
if (str1[i - 1] === str2[j - 1]) {
supersequence.push(str1[i - 1]);
i -= 1;
j -= 1;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
supersequence.push(str1[i - 1]);
i -= 1;
} else {
supersequence.push(str2[j - 1]);
j -= 1;
}
}
while (i > 0) {
supersequence.push(str1[i - 1]);
i -= 1;
}
while (j > 0) {
supersequence.push(str2[j - 1]);
j -= 1;
}
return supersequence.reverse().join('');
}
복잡도
- :
str1
의 길이, :str2
의 길이 - 시간 복잡도:
- 공간 복잡도: