LeetCode #139 Word Break: ต่อคำให้เต็มสตริงโดยไม่หลงทางซ้ำ

Word Break ให้สตริงกับพจนานุกรม แล้วถามว่าสามารถแบ่งสตริงทั้งหมดเป็นคำในพจนานุกรมได้หรือไม่ คำเดิมใช้ซ้ำได้ จุดหลอกคือการเลือกคำที่ดูถูกตอนต้นอาจพาไปทางตัน แต่ยังมีการแบ่งแบบอื่นที่สำเร็จครับ

ให้นึกถึงการปูกระเบื้องบนทางเดิน เราไม่ต้องจำลำดับกระเบื้องทุกแบบ แค่จำว่าตำแหน่งไหน “เดินมาถึงได้” แล้วลองวางแผ่นถัดไปจากจุดนั้น

วิธีที่ 1: Bottom-up DP — ค่าเริ่มต้นที่แนะนำ

ให้ dp[i] หมายถึง prefix ความยาว i แบ่งได้ ตั้ง dp[0] = True แล้วจากทุกจุดที่ถึงได้ ลองความยาวคำไม่เกินคำยาวสุด เวลา worst case O(n·L²) เพราะตัด substring และ hash โดย L คือความยาวคำสูงสุด; พื้นที่ O(n + จำนวนอักขระในพจนานุกรม) อ่านง่าย ไม่มี recursion limit และหยุดทันทีเมื่อถึงปลายสตริง

วิธีที่ 2: Memoized DFS

เริ่มที่ index ศูนย์ ลองทุกคำ แล้ว cache ว่า suffix ที่ index นี้ไปถึงปลายได้หรือไม่ State มี O(n) และเวลาคล้าย DP เหมาะเมื่ออธิบาย recursion ง่าย แต่ Python อาจชน recursion depth เมื่อสตริงยาว และ call stack เพิ่ม O(n)

วิธีที่ 3: BFS บนตำแหน่ง

มอง index เป็น node และคำที่ match เป็น edge ใช้ queue เดินไปยังปลายคำ พร้อม visited กันตรวจ suffix ซ้ำ เวลาและพื้นที่ใกล้ DP ข้อดีคือ mental model ชัดเมื่อจะต่อยอดหา “จำนวนคำต่ำสุด” แต่ overhead queue มากกว่า boolean DP เล็กน้อย

วิธีที่ 4: Trie + DP/DFS

สร้าง trie แล้วเดินตัวอักษรจากแต่ละ index โดยไม่สร้าง substring เหมาะเมื่อ dictionary ใหญ่ คำยาว และต้องตอบหลายสตริง แลกกับโค้ดและ memory ของ node ที่ซับซ้อนขึ้น

เงื่อนไข	เลือก	เหตุผล
input ทั่วไป อ่านง่าย	Bottom-up DP	invariant ตรงและไม่มี recursion
ต้องคืนเส้นทางแบ่งคำ	DP + parent	ย้อนสร้างคำตอบได้
dictionary ใช้ซ้ำหลาย query	Trie + DP	amortize ค่าสร้าง trie
memory จำกัด	DP แบบ boolean	O(n) และไม่เก็บทุกเส้นทาง
input มาเป็น stream	ต้อง buffer ก่อน	คำอาจคร่อม chunk และผลสุดท้ายยังกลับได้
input เรียงแล้ว	ไม่ช่วยโดยตรง	ลำดับตัวอักษรห้ามเปลี่ยน
แก้ input ได้	ไม่จำเป็น	algorithm อ่านอย่างเดียว

import unittest


def word_break(text, words):
    dictionary = set(words)
    max_len = max((len(word) for word in dictionary), default=0)
    reachable = [False] * (len(text) + 1)
    reachable[0] = True

    for start in range(len(text)):
        if not reachable[start]:
            continue
        for end in range(start + 1, min(len(text), start + max_len) + 1):
            if text[start:end] in dictionary:
                reachable[end] = True
        if reachable[-1]:
            return True
    return reachable[-1]


class WordBreakTests(unittest.TestCase):
    def test_reuses_a_word(self):
        self.assertTrue(word_break("applepenapple", ["apple", "pen"]))

    def test_greedy_prefix_is_not_enough(self):
        self.assertTrue(word_break("cars", ["car", "ca", "rs"]))

    def test_impossible_suffix(self):
        self.assertFalse(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))

    def test_empty_text(self):
        self.assertTrue(word_break("", []))


if __name__ == "__main__":
    unittest.main()

Edge cases และ trade-off

พจนานุกรมว่างกับสตริงไม่ว่างต้อง false ส่วนสตริงว่างสอดคล้องกับ dp[0] จึง true อย่าใช้ greedy เลือกคำยาวสุด เพราะ prefix เดียวอาจพาไปตัน ควรตัดคำซ้ำใน dictionary ด้วย set และจำกัด loop ด้วยความยาวคำสูงสุด

Recap

• นิยาม state ว่า prefix ไหนไปถึงได้
• ใช้ set และ max_len ลดงานที่ไม่จำเป็น
• เลือก trie เมื่อ dictionary ใหญ่และใช้ซ้ำ
• ทดสอบทางตัน, คำซ้ำ, dictionary ว่าง และสตริงว่าง
• ค่าเริ่มต้นภายใต้ constraints ของโจทย์: bottom-up DP