資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式：查詢最長公共子序列的長度
假設我們有兩個字串 text1 和 text2，我們需要找到它們的最長公共子序列的長度。眾所周知，字串的子序列是從原始字串中刪除一些字元（不改變剩餘字元的相對順序）生成的新字串。（例如，“abe”是“abcde”的子序列，但“adc”不是）。兩個字串的公共子序列是這兩個字串共有的子序列。如果沒有公共子序列，則返回 0。如果輸入為“abcde”和“ace”，則結果為 3。
為了解決這個問題，我們將遵循以下步驟：
n := s 的大小，m := x 的大小
如果 n 或 m 為 0，則返回 0
s := 空字串，連線 s
x := 空字串，連線 x
ret := 0
定義一個大小為 (n + 1) x (m + 1) 的矩陣 dp
對於 i 的範圍從 1 到 n
對於 j 的範圍從 1 到 m
dp[i, j] := dp[i, j - 1] 和 dp[i – 1, j] 的最大值
如果 s[i] = x[j]，則
dp[i, j] := 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;
int ret = 0;
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];
}
};
main(){
Solution ob;
cout << (ob.longestCommonSubsequence("abcde", "ace"));
}輸入
"abcde" "ace"
輸出
3
更新於: 2020年10月10日
204 次檢視
廣告