Tìm độ dài chuỗi từ rút gọn dài nhất trong Python

Cho từ điển words và chuỗi s. Tìm độ dài chuỗi dài nhất bắt đầu từ s, mỗi bước bỏ 1 ký tự vẫn là từ hợp lệ trong từ điển.

Ví dụ: words = ["lii","limit","limi","li","coffee","jug","pool","type"], s = "limit" → 4 (limit → limi → lii → li).

Giải pháp: Đệ quy + memoization (hoặc DP bottom-up). Với từ hiện tại, thử bỏ từng ký tự, nếu kết quả có trong từ điển thì đệ quy.

Ví dụ triển khai

class Solution:
    def solve(self, words, s):
        word_set = set(words)
        memo = {}
        def dfs(w):
            if w in memo:
                return memo[w]
            best = 1
            for i in range(len(w)):
                nxt = w[:i] + w[i+1:]
                if nxt in word_set:
                    best = max(best, 1 + dfs(nxt))
            memo[w] = best
            return best
        return dfs(s)

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

Đầu vào

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

Đầu ra

4