Giả sử chúng ta có một chuỗi không rỗng s và một từ điển có tên là wordDict, từ điển này chứa danh sách các từ không trống, hãy thêm dấu cách vào s để tạo một câu trong đó mỗi từ là một từ hợp lệ trong từ điển. Chúng ta phải tìm tất cả các câu có thể như vậy. “Appleraincoat” và từ điển là [“app”, “apple”, “rain”, “coat”, “raincoat”]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Tạo một bản ghi nhớ bản đồ
-
Xác định một phương thức được gọi là giải quyết, phương thức này sẽ lấy chuỗi và wordDict
-
nếu s là null thì trả về danh sách trống
-
nếu có trong bản ghi nhớ, thì -
-
trả lại [s] thư báo
-
-
tạo một mảng ret
-
cho tôi trong phạm vi từ 1 đến kích thước của s
-
nếu chuỗi con của s từ chỉ mục 0 đến i-1 có trong wordDict thì
-
cho j trong giải quyết (chuỗi con của s từ i đến cuối, wordDict)
-
p:=chuỗi con của s từ chỉ mục 0 đến i - 1, nối với khoảng trắng và j, sau đó xóa khoảng trắng thừa từ trái và phải -
-
chèn p vào ret
-
-
-
memo [s]:=ret
-
trả lại [s] thư báo
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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","rain coat"])) Đầu vào
"appleraincoat" ["app","apple","rain","coat","raincoat"]
Đầu ra
['apple rain coat', 'apple raincoat']