LeetCode 79 Word Search: backtracking ที่คืนสถานะกระดานทุกทางออก

โจทย์ Word Search ให้หาคำในตารางด้วยการเดินขึ้นลงซ้ายขวา โดยใช้ช่องเดิมซ้ำในเส้นทางเดียวไม่ได้ครับ รูปแบบนี้คือ backtracking: เลือกช่อง ทำเครื่องหมาย ลองต่อ แล้วคืนสถานะไม่ว่าพบหรือไม่พบ

วิธีที่ 1: visited set

เก็บพิกัดใน set ระหว่าง DFS โค้ดอธิบายง่ายและไม่แก้ board แต่ใช้ memory สูงสุด O(L) ตามความยาวคำ รวม call stack

วิธีที่ 2: in-place marking

เปลี่ยนตัวอักษรช่องที่ใช้อยู่เป็น sentinel ชั่วคราว แล้ว restore ก่อน return ลด visited structure เหลือ call stack O(L) แต่ต้องมั่นใจว่า sentinel ไม่ชน alphabet และคืนค่าทุก branch

วิธีที่ 3: frequency pruning + เลือกปลายคำ

นับอักษรบน board ก่อน หากคำต้องการตัวใดมากเกินให้ตอบ false ทันที แล้วเลือกค้นจากปลายที่พบได้น้อยกว่าเพื่อลด branching นี่ยังเป็น DFS เดิม แต่ลดงานเฉลี่ยโดยไม่เปลี่ยน worst case O(mn·4^L)

from collections import Counter
import unittest


def exist_with_set(board, word):
    if not word:
        return True
    rows, cols = len(board), len(board[0]) if board else 0

    def dfs(row, col, index, used):
        if index == len(word):
            return True
        if not (0 <= row < rows and 0 <= col < cols):
            return False
        if (row, col) in used or board[row][col] != word[index]:
            return False
        used.add((row, col))
        found = any(dfs(row + dr, col + dc, index + 1, used)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        used.remove((row, col))
        return found

    return any(dfs(row, col, 0, set()) for row in range(rows) for col in range(cols))


def exist_in_place(board, word):
    if not word:
        return True
    if not board or not board[0]:
        return False
    counts = Counter(char for row in board for char in row)
    if Counter(word) - counts:
        return False
    if counts[word[-1]] < counts[word[0]]:
        word = word[::-1]
    rows, cols = len(board), len(board[0])

    def dfs(row, col, index):
        if index == len(word):
            return True
        if not (0 <= row < rows and 0 <= col < cols) or board[row][col] != word[index]:
            return False
        saved = board[row][col]
        board[row][col] = None
        found = any(dfs(row + dr, col + dc, index + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[row][col] = saved
        return found

    return any(dfs(row, col, 0) for row in range(rows) for col in range(cols))


class WordSearchTests(unittest.TestCase):
    def check(self, board, word, expected):
        original = [row[:] for row in board]
        self.assertEqual(exist_with_set(board, word), expected)
        self.assertEqual(exist_in_place(board, word), expected)
        self.assertEqual(board, original)

    def test_paths_and_reuse(self):
        board = [list("ABCE"), list("SFCS"), list("ADEE")]
        self.check(board, "ABCCED", True)
        self.check(board, "SEE", True)
        self.check(board, "ABCB", False)

    def test_empty_and_frequency_pruning(self):
        self.check([], "A", False)
        self.check([["A"]], "", True)
        self.check([["A", "B"]], "AAA", False)


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

Decision table

สถานการณ์	Visited set	In-place mark	Frequency + start heuristic
readability	ดีที่สุด	ต้องระวัง restore	เพิ่มขั้นก่อน DFS
memory	O(L) set + stack	O(L) stack	O(alphabet) + stack
ห้ามแก้ input แม้ชั่วคราว	เหมาะ	ไม่เหมาะ	ใช้ร่วมกับ set ได้
board ใหญ่ คำหายจากความถี่	ยัง DFS	ยัง DFS	ตัดได้ทันที
input immutable	เหมาะ	ต้อง copy	เลือก backend ได้
ต้องคืน path จริง	เก็บ parent/path ง่าย	เพิ่ม path แยก	เป็น optimization เสริม

Best default: visited set สำหรับสัมภาษณ์เพราะ invariant ชัด; ใช้ in-place + frequency pruning เมื่อ memory/throughput สำคัญและ contract อนุญาต mutation ชั่วคราว

Edge cases

• board ว่างหรือแถวว่าง
• คำว่างต้องกำหนด contract แม้ constraints อาจไม่ให้มา
• ห้ามเดินทแยงและห้ามใช้ช่องซ้ำใน path เดียว
• ต้อง restore board แม้ branch พบคำสำเร็จ
• recursion depth เท่าความยาวคำ อาจต้อง stack เองนอก constraints ปกติ

Recap

• mark ก่อนเดิน และ unmark ทุกทางออก
• frequency pruning ลดงานแต่ไม่เปลี่ยน worst case
• เลือกปลายคำที่หายากเพื่อลดจุดเริ่ม
• ทดสอบว่า board หลังเรียกเหมือนเดิม