สมมติว่าเรามีสตริงที่ไม่ว่าง s และพจนานุกรมชื่อ wordDict พจนานุกรมนี้มีรายการคำที่ไม่ว่างเปล่า เพิ่มช่องว่างใน s เพื่อสร้างประโยคโดยที่แต่ละคำอยู่ คำในพจนานุกรมที่ถูกต้อง เราต้องหาประโยคที่เป็นไปได้ทั้งหมด “appleraincoat” และพจนานุกรมคือ [“app”, “apple”, “rain”, “coat”, “raincoat”]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างบันทึกแผนที่หนึ่งรายการ
-
กำหนดวิธีการที่เรียกว่า Solve ซึ่งจะใช้ string และ wordDict
-
ถ้า s เป็นค่าว่าง ให้คืนค่ารายการว่าง
-
ถ้าอยู่ในบันทึกแล้ว −
-
บันทึกการส่งคืน[s]
-
-
สร้างอาร์เรย์ ret
-
สำหรับผมอยู่ในช่วง 1 ถึงขนาด s
-
ถ้าสตริงย่อยของ s จากดัชนี 0 ถึง i – 1 มีอยู่ใน wordDict แล้ว
-
สำหรับ j ในการแก้ปัญหา (สตริงย่อยของ s จาก i ไปยังจุดสิ้นสุด wordDict)
-
p :=สตริงย่อยของ s จากดัชนี 0 ถึง i – 1 เชื่อมด้วยช่องว่างและ j จากนั้นล้างช่องว่างเพิ่มเติมจากด้านซ้ายและขวา −
-
แทรก p ลงใน ret
-
-
-
บันทึก[s] :=ย้อนหลัง
-
บันทึกการส่งคืน[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","rain coat"])) อินพุต
"appleraincoat" ["app","apple","rain","coat","raincoat"]
ผลลัพธ์
['apple rain coat', 'apple raincoat']
