Word Break ใน Python - ตรวจสอบการแบ่งคำจาก Dictionary

สมมติว่าเรามีสตริงไม่ว่าง s และ dictionary wordDict ที่มีรายการคำไม่ว่าง ให้กำหนดว่า s สามารถแบ่งเป็นลำดับคำจาก dictionary คั่นด้วยช่องว่างได้หรือไม่ กฎ:

• คำเดียวกันใน dictionary อาจใช้ซ้ำได้หลายครั้ง
• สมมติว่า dictionary ไม่มีคำซ้ำ

ตัวอย่าง s = "applepenapple" และ word dictionary ["apple", "pen"] ผลลัพธ์คือ true เพราะ s แบ่งได้เป็น "apple pen apple"

ขั้นตอนการทำงาน (Dynamic Programming)

1. สร้างเมทริกซ์ DP ขนาด n x n โดย n = ความยาวสตริง เริ่มต้นด้วย false
2. วนลูป i จาก 1 ถึงความยาวของ s:
   • วนลูป j จาก 0 ถึงความยาวของ s - i:
     • ถ้า substring s[j:j+i] อยู่ใน dictionary ให้ 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] := True
3. คืนค่า DP[0][len(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):
                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