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 次檢視

開啟您的 職業生涯

完成課程獲得認證

開始學習
廣告