Chương trình tìm độ dài của chuỗi từ giảm dần dài nhất trong Python?

Giả sử chúng ta có một danh sách các từ hợp lệ và cũng có một chuỗi s, chúng ta phải tìm độ dài của chuỗi các từ giảm dần dài nhất có thể được tạo ra bằng cách bắt đầu từ s và loại bỏ các chuỗi đơn và vẫn tạo ra các từ hợp lệ.

Vì vậy, nếu đầu vào giống như words =["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"] s ="limit", thì đầu ra sẽ là 4, vì chúng ta có thể tạo chuỗi, bắt đầu từ từ "giới hạn", "giới hạn" -> "limi" -> "lii" -> "li".

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

• Định nghĩa một hàm giải quyết (). Điều này sẽ diễn ra thành lời, s

• max_num:=0

• đối với mỗi tôi trong lời nói, hãy làm

  • nếu tôi giống với s, thì

    • đối với j trong phạm vi 0 đến kích thước của s, thực hiện

      • max_num:=tối đa 1 + giải (từ, s [từ chỉ mục 0 đến j-1] nối s [từ chỉ mục j + 1 đến cuối]) và max_num

• trả về max_num

Ví dụ

class Solution:
   def solve(self, words, s):
      max_num = 0
      for i in words:
         if i == s:
            for j in range(len(s)):
               max_num = max(1 + self.solve(words, s[:j] + s[j + 1 :]), max_num)
      return max_num

ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))

Đầu vào

["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"],"limit"

Đầu ra

4