หาความยาวโซ่คำ Diminishing ที่ยาวที่สุดใน Python

มีลิสต์คำที่ถูกต้องและสตริง s หาความยาวโซ่ยาวที่สุดที่ลบตัวอักษรทีละตัวจาก s ได้คำในลิสต์ทุกขั้น

ตัวอย่าง: words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"], s = "limit" → 4 (limit → limi → lii → li)

แนวทาง (Recursive DFS)

1. ฟังก์ชัน solve(words, s) คืนความยาวโซ่สูงสุดจาก s
2. ถ้า s ไม่อยู่ใน words → คืน 0
3. ลองลบตัวอักษรแต่ละตำแหน่ง j ใน s เรียก solve ซ้ำ
4. คืน 1 + max(...)

ตัวอย่างโค้ด

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))  # 4

อินพุต

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

เอาต์พุต

4

หมายเหตุ

โค้ดนี้ยังไม่มี Memoization อาจช้าสำหรับ input ใหญ่ ควรเพิ่ม @lru_cache