สมมติว่าเรามีสตริงสองตัวคือ text1 และ text2 เราต้องการหาความยาวของลำดับย่อยร่วมที่ยาวที่สุด (Longest Common Subsequence - LCS) ลำดับย่อยคือลำดับที่สร้างจากสตริงต้นฉบับโดยการลบตัวอักษรบางส่วนออกไปโดยไม่เปลี่ยนลำดับของตัวอักษรที่เหลือ (เช่น "abe" เป็นลำดับย่อยของ "abcde" แต่ "adc" ไม่ใช่) ลำดับย่อยร่วมคือลำดับย่อยที่ปรากฏในทั้งสองสตริง หากไม่มีลำดับย่อยร่วม ให้คืนค่า 0
เช่น หากอินพุตคือ "abcde" และ "ace" ผลลัพธ์จะเป็น 3
ขั้นตอนการแก้ปัญหา
- กำหนด n = ความยาวของ s, m = ความยาวของ x
- ถ้า n = 0 หรือ m = 0 ให้คืนค่า 0
- เพิ่มช่องว่างหน้าสตริงทั้งสอง (เพื่อทำให้ดัชนีเริ่มจาก 1)
- สร้างตาราง dp ขนาด (n+1) x (m+1)
- วนลูป i จาก 1 ถึง n, j จาก 1 ถึง m:
- dp[i][j] = max(dp[i][j-1], dp[i-1][j])
- ถ้า s[i] = x[j]: dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1])
- คืนค่า dp[n][m]
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestCommonSubsequence(string s, string x) {
int n = s.size();
int m = x.size();
if (!n || !m) return 0;
s = " " + s;
x = " " + x;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
if (s[i] == x[j]) {
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
}
return dp[n][m];
}
};
int main() {
Solution ob;
cout << (ob.longestCommonSubsequence("abcde", "ace"));
}
อินพุต
"abcde" "ace"
เอาต์พุต
3
