在Python中找到最短超序列的长度

假设我们有两个字符串s和t。我们必须找到具有s和t作为子序列的字符串的最短长度。

因此，如果输入为s =“pipe” t =“people”，则输出为7，因为一个可能的超序列为“pieople”。

为了解决这个问题，我们将按照以下步骤进行−

m：s的大小，n：t的大小
table：大小为(n + 1) x (m + 1)的表，填充为0
for i在0到m的范围内，do
- for j在0到n的范围内，do
  - 如果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))