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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告