โปรแกรมตรวจสอบว่าสตริงสามารถแบ่งเป็นคำจากรายการที่กำหนดได้หรือไม่ใน Python

โจทย์ Word Break: ให้ลิสต์คำ words และสตริง s (ไม่มีช่องว่าง) ตรวจสอบว่า s แบ่งเป็นคำใน words ได้หมดหรือไม่

ตัวอย่าง: words = ["love", "python", "we", "programming", "language"], s = "welovepythonprogramming" → True

อัลกอริธึม Recursion + Memoization (นี่ใช้ recursion แบบง่าย)

• แปลง words เป็น set เพื่อ O(1) lookup
• ฟังก์ชัน rec(i): ตรวจสอบจากตำแหน่ง i ถึงสิ้นสุด
• สร้าง substring acc เพิ่มทีละตัวอักษร ถ้าอยู่ใน words ให้เรียก rec(j+1)

การนำไปใช้

class Solution:
    def solve(self, words, s):
        words = set(words)
        def rec(i=0):
            if i == len(s):
                return True
            acc = ""
            for j in range(i, len(s)):
                acc += s[j]
                if acc in words:
                    if rec(j + 1):
                        return True
            return False
        return rec()

ob = Solution()
words = ["love", "python", "we", "programming", "language"]
s = "welovepythonprogramming"
print(ob.solve(words, s))  # True