資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中執行兩個字串的字首壓縮程式
假設我們有兩個字串 s 和 t（都包含小寫英文字母）。我們需要找到一個大小為 3 的對列表，其中每個對都具有以下形式 (l, k)，其中 k 是一個字串，l 是其長度。現在在這三個對中，第一個包含 s 和 t 的子字串，它是這兩個字串的最長公共字首 p，然後 s 的剩餘部分是 s'，t 的剩餘部分是 t'。所以最終列表將如下所示：[(p 的長度, p), (s' 的長度, s'), (t' 的長度, t')]。
因此，如果輸入類似於 s = "science" t = "school"，則輸出將為 [(2, 'sc'), (5, 'ience'), (4, 'hool')]
為了解決這個問題，我們將遵循以下步驟：
- lcp := 空字串
- 對於 i 從 0 到 s 或 t 的大小的最小值，執行以下操作
- 如果 s[i] 與 t[i] 相同，則
- lcp := lcp + s[i]
- 如果 s[i] 與 t[i] 相同，則
- s_rem := 從索引 (lcp 的大小) 到末尾的 s 的子字串
- t_rem := 從索引 (lcp 的大小) 到末尾的 t 的子字串
- 返回三個對的列表 [(lcp 的大小 , lcp) ,(s_rem 的大小 , s_rem) ,(t_rem 的大小 , t_rem)]
示例
讓我們看看以下實現以獲得更好的理解：
def solve(s, t): lcp = '' for i in range(min(len(s), len(t))): if s[i] == t[i]: lcp += s[i] s_rem = s[len(lcp):] t_rem = t[len(lcp):] return [(len(lcp), lcp), (len(s_rem), s_rem), (len(t_rem), t_rem)] s = "science" t = "school" print(solve(s, t))
輸入
"science", "school"
輸出
[(2, 'sc'), (5, 'ience'), (4, 'hool')]
更新於: 2021 年 10 月 12 日
253 次檢視
廣告