数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告