LeetCode - 가장 긴 공통 하위 시퀀스
29418 단어 programminggojavascriptalgorithms
문제 설명
두 개의 문자열 text1과 text2가 주어지면 가장 긴 공통 하위 시퀀스의 길이를 반환합니다. 공통 하위 시퀀스가 없으면 0을 반환합니다.
문자열의 하위 시퀀스는 나머지 문자의 상대 순서를 변경하지 않고 일부 문자(없을 수 있음)가 삭제된 원래 문자열에서 생성된 새 문자열입니다.
두 문자열의 공통 하위 시퀀스는 두 문자열에 공통인 하위 시퀀스입니다.
문제 진술 출처: https://leetcode.com/problems/longest-common-subsequence
예 1:
Input: text1 = 'abcde', text2 = 'ace'
Output: 3
Explanation: The longest common subsequence is 'ace' and its length is 3.
예 2:
Input: text1 = 'abc', text2 = 'abc'
Output: 3
Explanation: The longest common subsequence is 'abc' and its length is 3.
예 3:
Input: text1 = 'abc', text2 = 'def'
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
제약:
- 1 <= text1.length, text2.length <= 1000
- text1 and text2 consist of only lowercase English characters.
설명
재귀
순진한 해결책은 text1[1..n]의 모든 하위 시퀀스를 확인하여 그것이 또한 text2[1..m]의 하위 시퀀스인지 확인하는 것입니다. 이를 달성하기 위해 솔루션이 사소해질 때까지 문제를 더 작은 하위 문제로 나눌 수 있습니다. 문제를 하위 문제로 나누기 위해 마지막 요소를 제거하여 각 시퀀스를 줄입니다. 단축된 문자열에 대해 동일한 작업을 재귀적으로 수행하고 문자열의 첫 번째 문자에 도달할 때까지 마지막 부분을 계속 가져옵니다.
문자열의 마지막 문자를 제거하는 것은 두 가지 상황에 따라 다릅니다.
LCS(text1[1..n], text2[1..m]) = LCS(text1[1..n - 1], text2[1..m - 1]) if text1[n] == text2[m]
이를 이해하기 위해 예를 들어보자.
text1 = 'abc'
text2 = 'abcde'
text1은 c로 끝나고 text2는 e로 끝납니다. 문자열 text2에서 마지막 문자 e를 제거하고 문제를 LCS(text1[1..n], text2[1..m - 1])로 줄일 수 있습니다.
마찬가지로 문자열 text1에서 마지막 문자 c를 제거하고 문제를 LCS(text1[1..n - 1], text2[1..m])로 줄입니다. 가장 긴 공통 하위 시퀀스의 길이를 계산하려고 합니다. 아래 접근 방식을 사용하여 이 경우를 처리합니다.
LCS(text1[1..n], text2[1..m]) = max(LCS(text1[1..n], text2[1..m - 1]), LCS(text1[1..n - 1], text2[1..m]))
위 접근 방식의 C++ 스니펫은 다음과 같습니다.
int lcsLength(string text1, string text2, int n, int m) {
if(n == 0 || m == 0) {
return 0;
}
if(text1[n - 1] == text2[m - 1]) {
return lcsLength(text1, text2, n - 1, m - 1) + 1;
}
return max(lcsLength(X, Y, m, n - 1), lcsLength(X, Y, m - 1, n));
}
위 접근법의 시간복잡도는 O(2^(n + m))이고 공간복잡도는 O(1)이다.
동적 프로그래밍
위의 접근 방식에는 중복되는 하위 문제가 있습니다. 중첩되는 하위 문제를 확인하기 위해 위의 예제에 대한 부분 재귀 트리를 구성해 봅시다.
text1 = 'abc'
text2 = 'abcde'
n = text1.length
= 3
m = text2.length
= 5
(3, 5)
________|_________
| |
(2, 5) (3, 4)
| |
_____________| |_____________
| | | |
(1, 5) (2, 4) (2, 4) (3, 3)
(2, 4) is computed twice.
하위 문제 (2, 4)는 두 번 계산됩니다. 우리는 최적의 하위 구조와 겹치는 하위 문제가 있는 문제는 동적 프로그래밍으로 해결할 수 있음을 알고 있습니다.
먼저 알고리즘을 확인해 봅시다.
- set n = text1.size()
m = text2.size()
- initialize 2D array int dp[n + 1][m + 1]
- loop for i = 1; i <= n; i++
loop for j = 1; j <= m; j++
if text1[i - 1] == text2[j - 1]
- update dp[i][j] = dp[i - 1][j - 1] + 1
else
- update dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
- return dp[n][m]
위 방식의 시간복잡도는 O(N * M)이고 공간복잡도는 O(N * M)이다.
C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.
C++ 솔루션
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size();
int m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[n][m];
}
};
골랑 솔루션
func longestCommonSubsequence(text1 string, text2 string) int {
n := len(text1)
m := len(text2)
dp := make([][]int, n + 1)
for i := range dp {
dp[i] = make([]int, m + 1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if text1[i - 1] == text2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
}
}
}
return dp[n][m]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
자바스크립트 솔루션
var longestCommonSubsequence = function(text1, text2) {
let n = text1.length;
let m = text2.length;
let dp = new Array(n + 1).fill(0);
for (let i = 0; i < n + 1; i++) {
dp[i] = new Array(m + 1).fill(0);
}
for(let i = 1; i <= n; i++) {
for(let j = 1; j <= m; j++) {
if(text1[i - 1] == text2[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]);
}
}
}
return dp[n][m];
};
예제 1의 알고리즘을 시험 실행해 보겠습니다.
Input: text1 = 'abcde'
text2 = 'ace'
Step 1: n = text1.size()
= 5
m = text2.size()
= 3
Step 2: dp(n + 1, vector<int>(m + 1, 0))
dp = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
Step 3: loop for i = 1; i <= n
1 <= 5
true
loop for j = 1; j <= m
1 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[0] == text2[0]
'a' == 'a'
true
dp[i][j] = dp[i - 1][j - 1] + 1
dp[1][1] = dp[0][0] + 1
= 1
j++
j = 2
loop for j <= m
2 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[0] == text2[1]
'a' == 'c'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[1][2] = max(dp[1][1], dp[0][2])
= max(1, 0)
= 1
j++
j = 3
loop for j <= m
3 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[0] == text2[2]
'a' == 'e'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[1][3] = max(dp[1][2], dp[0][3])
= max(1, 0)
= 1
j++
j = 4
loop for j <= m
4 <= 3
false
i++
i = 2
dp = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
Step 4: loop for i = 1; i <= n
2 <= 5
true
loop for j = 1; j <= m
1 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[1] == text2[0]
'b' == 'a'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[2][1] = max(dp[2][0], dp[1][1])
= max(0, 1)
= 1
j++
j = 2
loop for j = 1; j <= m
2 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[1] == text2[1]
'b' == 'c'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[2][2] = max(dp[2][1], dp[1][2])
= max(1, 1)
= 1
j++
j = 3
loop for j = 1; j <= m
3 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[1] == text2[2]
'b' == 'e'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[2][3] = max(dp[2][2], dp[1][3])
= max(1, 1)
= 1
j++
j = 4
loop for j <= m
4 <= 3
false
i++
i = 3
dp = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
Step 5: loop for i = 1; i <= n
3 <= 5
true
loop for j = 1; j <= m
1 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[3] == text2[0]
'c' == 'a'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[3][1] = max(dp[3][0], dp[2][1])
= max(0, 1)
= 1
j++
j = 2
loop for j = 1; j <= m
2 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[2] == text2[1]
'c' == 'c'
true
dp[i][j] = dp[i - 1][j - 1] + 1
dp[3][2] = dp[2][1] + 1
= 1 + 1
= 2
j++
j = 3
loop for j = 1; j <= m
3 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[2] == text2[2]
'c' == 'e'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[3][3] = max(dp[3][2], dp[2][3])
= max(2, 1)
= 2
j++
j = 4
loop for j <= m
4 <= 3
false
i++
i = 4
dp = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 2, 2],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
Step 6: loop for i = 1; i <= n
4 <= 5
true
loop for j = 1; j <= m
1 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[3] == text2[0]
'd' == 'a'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[4][1] = max(dp[4][0], dp[3][1])
= max(0, 1)
= 1
j++
j = 2
loop for j = 1; j <= m
2 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[3] == text2[1]
'd' == 'c'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[4][2] = max(dp[4][1], dp[3][2])
= max(1, 2)
= 2
j++
j = 3
loop for j = 1; j <= m
3 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[3] == text2[2]
'd' == 'e'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[4][3] = max(dp[4][2], dp[3][3])
= max(2, 2)
= 2
j++
j = 4
loop for j <= m
4 <= 3
false
i++
i = 5
dp = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 2, 2],
[0, 1, 2, 2],
[0, 0, 0, 0]
]
Step 7: loop for i = 1; i <= n
5 <= 5
true
loop for j = 1; j <= m
1 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[4] == text2[0]
'e' == 'a'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[5][1] = max(dp[5][0], dp[4][1])
= max(0, 1)
= 1
j++
j = 2
loop for j = 1; j <= m
2 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[4] == text2[1]
'e' == 'c'
false
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
dp[5][2] = max(dp[5][1], dp[4][2])
= max(1, 2)
= 2
j++
j = 3
loop for j = 1; j <= m
3 <= 3
true
if text1[i - 1] == text2[j - 1]
text1[4] == text2[3]
'e' == 'e'
true
dp[i][j] = dp[i - 1][j - 1] + 1
dp[5][3] = dp[4][2] + 1
= 2 + 1
= 3
j++
j = 4
loop for j <= m
4 <= 3
false
i++
i = 6
dp = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 1, 1, 1],
[0, 1, 2, 2],
[0, 1, 2, 2],
[0, 1, 2, 3]
]
Step 8: loop for i = 1; i <= n
6 <= 5
false
Step 9: return dp[n][m]
dp[5][3] = 3
We return the answer as 3.
Reference
이 문제에 관하여(LeetCode - 가장 긴 공통 하위 시퀀스), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/_alkesh26/leetcode-longest-common-subsequence-16h2텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
