資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
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 為 0 或 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年4月30日
367 次瀏覽
廣告