資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢三個字串的最長公共子序列長度
假設我們有三個字串 s1、s2 和 s3，我們需要找到它們的最長公共子序列的長度。
例如，如果輸入是 s1 = "ababchemxde" s2 = "pyakcimde" s3 = "oauctime"，則輸出為 4，因為最長公共子序列是 "acme"。
為了解決這個問題，我們將遵循以下步驟：
- m := s1 的長度，n := s2 的長度，o := s3 的長度
- dp := 一個大小為 (o + 1) x (n + 1) x (m + 1) 的 3D 矩陣
- 對於 i 從 1 到 m，執行：
- 對於 j 從 1 到 n，執行：
- 對於 k 從 1 到 o，執行：
- 如果 s1[i - 1]、s2[j - 1]、s3[k - 1] 相同，則
- dp[i, j, k] := 1 + dp[i - 1, j - 1, k - 1]
- 否則，
- dp[i, j, k] = dp[i - 1, j, k]、dp[i, j - 1, k] 和 dp[i, j, k - 1] 的最大值
- 如果 s1[i - 1]、s2[j - 1]、s3[k - 1] 相同，則
- 對於 k 從 1 到 o，執行：
- 對於 j 從 1 到 n，執行：
- 返回 dp[m, n, o]
示例 (Python)
讓我們看看下面的實現來更好地理解：
class Solution: def solve(self, s1, s2, s3): m = len(s1) n = len(s2) o = len(s3) dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): for k in range(1, o + 1): if s1[i - 1] == s2[j - 1] == s3[k - 1]: dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1] else: dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]) return dp[m][n][o] ob = Solution() s1 = "ababchemxde" s2 = "pyakcimde" s3 = "oauctime" print(ob.solve(s1, s2, s3))
輸入
"ababchemxde", "pyakcimde", "oauctime"
輸出
4
更新於：2020年12月12日
604 次瀏覽
廣告