Tách từ II trong Python

Giả sử chúng ta có một chuỗi không rỗng s và một từ điển wordDict chứa các từ không rỗng. Chèn khoảng trắng vào s để tạo thành câu mà mỗi từ đều có trong từ điển. Tìm tất cả các câu có thể.

Ví dụ: "appleraincoat" với từ điển ["app", "apple", "rain", "coat", "raincoat"].

Các bước giải quyết (DP + Memoization):

• Tạo map memo lưu kết quả cho từng chuỗi con
• Hàm solve(s, wordDict): nếu s rỗng trả về [""]; nếu s trong memo trả về memo[s]
• Duyệt i từ 1 đến len(s): nếu s[:i] trong wordDict, đệ quy solve(s[i:]) và ghép từ
• Lưu vào memo và trả về

Ví dụ

class Solution(object):
    def wordBreak(self, s, wordDict):
        self.memo = {}
        wordDict = set(wordDict)
        return self.solve(s, wordDict)
    def solve(self, s, wordDict):
        if not s:
            return ['']
        if s in self.memo:
            return self.memo[s]
        ret = []
        for i in range(1, len(s)+1):
            if s[:i] in wordDict:
                for j in self.solve(s[i:], wordDict):
                    ret.append((s[:i] + " " + j).strip())
        self.memo[s] = ret
        return self.memo[s]

ob = Solution()
print(ob.wordBreak("appleraincoat", ["app","apple","rain","coat","raincoat"]))

Đầu vào

"appleraincoat" ["app","apple","rain","coat","raincoat"]

Đầu ra

['apple rain coat', 'apple raincoat']