1143. Longest Common Subsequence
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu càu tìm độ dài dãy con chung dài nhất của hai chuỗi (không nhất thiết liên tiếp, chỉ cần giữ thứ tự). Đây là một bài toán kinh điển về DP
Approach
text1 có độ dài m, text2 có độ dài ndp kích thước (m+1) x (n+1), trong đó dp[i][j] là độ dài LCS của text1[0..i-1] và text2[0..j-1].text1[i - 1] === text2[j - 1] thì dp[i - 1][j - 1] + 1 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) dp[m][n]Solution
1function longestCommonSubsequence(text1: string, text2: string): number {
2 const m = text1.length;
3 const n = text2.length;
4
5 const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
6 for (let i = 1; i <= m; i++) {
7 for (let j = 1; j <= n; j++) {
8 if (text1[i - 1] === text2[j - 1]) {
9 dp[i][j] = dp[i - 1][j - 1] + 1;
10 } else {
11 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
12 }
13 }
14 }
15
16 return dp[m][n]
17};Solution - optimize
1function longestCommonSubsequence(text1: string, text2: string): number {
2 if(text1.length < text2.length) {
3 [text1, text2] = [text2, text1];
4 }
5
6 const m = text1.legnth;
7 const n = text2.length;
8
9 let prev = Array(m + 1).fill(0);
10 let curr = Array(n + 1).fill(0);
11
12 for(let i = 1; i <= m; i++) {
13 for(let j = 1; j <= n; j++) {
14 if(text1[i - 1] === text2[j - 1]) {
15 curr[j] = prev[j - 1] + 1;
16 } else {
17 curr[j] = Math.max(prev[j], curr[j - 1]);
18 }
19 }
20
21 [prev, curr] = [curr, prev]
22 }
23
24 return prev[n]
25};