数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找最短超序列的长度
假设我们有两个字符串 s 和 t。我们需要找到包含 s 和 t 作为子序列的最短字符串的长度。
因此，如果输入类似于 s = "pipe" t = "people"，则输出将为 7，因为一个可能的超序列是 "pieople"。
为了解决这个问题，我们将遵循以下步骤：
m := s 的大小，n := t 的大小
table := 一个大小为 (n + 1) x (m + 1) 的表格，并用 0 填充
对于 i 从 0 到 m，执行
对于 j 从 0 到 n，执行
如果 i 等于 0 或 j 等于 0，则
table[i, j] := 0
否则，
如果 s[i - 1] 等于 t[j - 1]，则
table[i, j] := 1 + table[i - 1, j - 1]
否则，
table[i, j] = table[i, j - 1] 和 table[i - 1, j] 的最大值
返回 m + n - table[m, n]
示例
让我们看看下面的实现来更好地理解：
class Solution: def solve(self, s, t): m = len(s) n = len(t) table = [[0 for i in range(n + 1)] for j in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: table[i][j] = 0 else: if s[i - 1] == t[j - 1]: table[i][j] = 1 + table[i - 1][j - 1] else: table[i][j] = max(table[i][j - 1], table[i - 1][j]) return m + n - table[m][n] ob = Solution() s = "pipe" t = "people" print(ob.solve(s, t))
输入
"pipe", "people"
输出
7
更新于: 2020-12-22
133 次浏览
广告