Chương trình tìm độ dài của siêu nhỏ ngắn nhất trong Python

Giả sử chúng ta có hai chuỗi s và t. Chúng ta phải tìm độ dài của chuỗi ngắn nhất có cả s và t là dãy con.

Vì vậy, nếu đầu vào giống như s ="pipe" t ="people", thì đầu ra sẽ là 7, vì một điểm siêu thường có thể xảy ra là "pieople".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=kích thước của s, n:=kích thước của t

• table:=một bảng có kích thước (n + 1) x (m + 1) và điền bằng 0

• đối với tôi trong phạm vi từ 0 đến m, hãy thực hiện

  • đối với j trong phạm vi từ 0 đến n, thực hiện

    • nếu tôi giống 0 hoặc j giống 0 thì

      • bảng [i, j]:=0

    • nếu không,

      • nếu s [i - 1] giống với t [j - 1] thì

        • bảng [i, j]:=1 + bảng [i - 1, j - 1]

      • nếu không,

        • table [i, j] =tối đa của table [i, j - 1] và table [i - 1, j]

• trả về m + n - bảng [m, n]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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))

Đầu vào

"pipe", "people"

Đầu ra

7