สมมติว่าเรามีสตริงที่ไม่ว่างหนึ่งสตริงและพจนานุกรม wordDict ที่ประกอบด้วยรายการของคำที่ไม่ว่างเปล่า กำหนดเมื่อ s สามารถแบ่งออกเป็นลำดับที่คั่นด้วยช่องว่างของคำในพจนานุกรมตั้งแต่หนึ่งคำขึ้นไป เราต้องปฏิบัติตามกฎบางอย่าง -
- คำเดียวกันในพจนานุกรมอาจถูกนำมาใช้ซ้ำหลายครั้งในการแบ่งกลุ่ม
- เราสามารถสรุปได้ว่าพจนานุกรมไม่มีคำซ้ำกัน
สมมติว่าสตริง s =“applepenapple” และพจนานุกรมคำเหมือนกับ [“apple”, “pen”] จากนั้นผลลัพธ์จะเป็นจริงเพราะสตริง s สามารถแบ่งส่วนเป็น “apple pen apple” ได้
ให้เราดูขั้นตอน -
- กำหนดหนึ่งเมทริกซ์ DP ของคำสั่ง n x n n =ขนาดของสตริง และเริ่มต้นด้วย false
- สำหรับ i ในช่วง 1 ถึงความยาวของ s
- สำหรับ j ในช่วง 0 ถึงความยาวของ s – i
- หากสตริงย่อย s[j ถึง j + 1] ในพจนานุกรม จากนั้น dp[j, j+i - 1] :=True
- อย่างอื่น
- สำหรับ k ในช่วง j + 1 ถึง j + i
- ถ้า dp[j, k - 1] และ dp[k, j + i – 1] แล้ว dp[j, j + i – 1] :=จริง
- สำหรับ k ในช่วง j + 1 ถึง j + i
- สำหรับ j ในช่วง 0 ถึงความยาวของ s – i
- ผลตอบแทน DP[0, ความยาวของ s - 1]
ตัวอย่าง(Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object):
def wordBreak(self, s, wordDict):
dp = [[False for i in range(len(s))] for x in range(len(s))]
for i in range(1,len(s)+1):
for j in range(len(s)-i+1):
#print(s[j:j+i])
if s[j:j+i] in wordDict:
dp[j][j+i-1] = True
else:
for k in range(j+1,j+i):
if dp[j][k-1] and dp[k][j+i-1]:
dp[j][j+i-1]= True
return dp[0][len(s) - 1]
ob1 = Solution()
print(ob1.wordBreak("applepenapple", ["apple", "pen"])) อินพุต
"applepenapple" ["apple", "pen"]
ผลลัพธ์
true
