資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢兩個給定字串公共特殊子串的長度
假設我們有兩個字串 s1 和 s2。我們需要找到最長字串 s3 的長度，該字串是 s1 和 s2 的公共特殊子串。
我們可以說字串 x 是另一個字串 y 的特殊子串，如果 x 可以透過從 y 中刪除 0 個或多個字元生成。
因此，如果輸入為 s1 = 'pineapple' s2 = 'people'，則輸出為 5，因為特殊子串為 'peple'，長度為 5。
為了解決這個問題，我們將遵循以下步驟：
- prev := 一個新的字典，如果某個鍵不存在，則返回 0
- 對於 i in range(0, len(s1) - 1):
- cur := 一個新的字典，如果某個鍵不存在，則返回 0
- 對於 j in range(0, len(s2) - 1):
- 當 s1[i] 等於 s2[j] 時，cur[j] := prev[j - 1] + 1；否則，cur[j] := max(cur[j - 1], prev[j])
- prev := cur
- 返回 prev[len(s2) - 1]
示例
讓我們看下面的實現來更好地理解：
from collections import defaultdict def solve(s1, s2): prev = defaultdict(int) for i in range(len(s1)): cur = defaultdict(int) for j in range(len(s2)): cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j]) prev = cur return prev[len(s2)-1] s1 = 'pineapple' s2 = 'people' print(solve(s1, s2))
輸入
'pineapple', 'people'
輸出
5
更新於：2021年10月11日
瀏覽量：104
廣告