กำหนดสตริง s และ dictionary wordDict (ลิสต์คำ) ต้องแทรกช่องว่างใน s เพื่อสร้างประโยคที่ทุกคำอยู่ใน wordDict หาทุกประโยคที่เป็นไปได้
ตัวอย่าง: s = "appleraincoat", wordDict = ["app","apple","rain","coat","raincoat"] → ["apple rain coat", "apple raincoat"]
ขั้นตอนการแก้ปัญหา
- ใช้ memoization (dictionary memo) เก็บผลลัพธ์ของ substring
- ฟังก์ชัน solve(s, wordDict): ถ้า s ว่าง คืน [""]; ถ้ามีใน memo คืน memo[s]
- วน i จาก 1 ถึง len(s): ถ้า s[:i] ใน wordDict ให้เรียก solve(s[i:]) แล้วนำมารวมกับ s[:i]
- เก็บใน memo[s] และคืนค่า
ตัวอย่างโค้ด
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"]))อินพุต
"appleraincoat" ["app","apple","rain","coat","raincoat"]
เอาต์พุต
['apple rain coat', 'apple raincoat']
