On this page

ข้อ 66 · LC72 Edit Distance (ระยะแก้ไข) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

หาจำนวน edit น้อยสุดเพื่อเปลี่ยน string หนึ่งเป็นอีก string ด้วย 2D DP ต้นแบบ

โจทย์ (LC72): กำหนด string (สตริง) สองตัวคือ word1 และ word2 มา ให้หาจำนวน operation (การกระทำ) น้อยที่สุดที่ต้องใช้เพื่อแปลง word1 ให้กลายเป็น word2 โดย operation ที่ทำได้บน word1 มีสามแบบ ได้แก่ insert ตัวอักษรหนึ่งตัว, delete ตัวอักษรหนึ่งตัว หรือ replace ตัวอักษรหนึ่งตัว

Example 1

Input:: word1 = "horse", word2 = "ros"
Output:: 3
Explanation:: horse → rorse (replace 'h' เป็น 'r') → rose (delete 'r') → ros (delete 'e')

Example 2

Input:: word1 = "intention", word2 = "execution"
Output:: 5

Example 3

Input:: word1 = "", word2 = "abc"
Output:: 3
Explanation:: word1 เป็น string ว่าง ต้อง insert ทั้ง 3 ตัวเพื่อให้กลายเป็น "abc"

Constraints (ข้อจำกัด)

0 <= word1.length, word2.length <= 500
word1 และ word2 เป็นตัวอักษรอังกฤษพิมพ์เล็ก

แนวทาง — ต้องใช้อะไร & คิดยังไง

นี่คือ 2D DP ต้นแบบเลย define dp[i][j] = จำนวน edit น้อยสุดเพื่อเปลี่ยน word1 ตัวแรก i ตัว ให้เป็น word2 ตัวแรก j ตัว transition แบ่งสองกรณี: ถ้าตัวอักษรท้ายสุดตรงกันไม่ต้องแก้ (ลอกทแยง) ถ้าไม่ตรงเลือก 1 + min ของสามทาง

สามทางนั้นจับคู่กับสามทิศของเพื่อนบ้าน: delete ตัวจาก word1 = มาจากช่องบน dp[i-1][j], insert ตัวเข้า word1 = มาจากช่องซ้าย dp[i][j-1], replace ตัว = มาจากช่องทแยง dp[i-1][j-1] การจับทิศให้ตรงความหมายช่วยไม่ให้งงเวลาเขียนสูตร

สร้าง table dp ขนาด (m+1) x (n+1)
ตั้ง base case ขอบ: dp[i][0] = i (delete i ตัวให้เป็น empty string), dp[0][j] = j (insert j ตัวจาก empty string)
iterate i, j จาก 1 ขึ้นไป
ถ้า word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (ไม่ต้องแก้)
ถ้าไม่ตรง: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]

จุดพลาดที่พบบ่อย

base case ขอบสำคัญมากและคนมักลืม: dp[i][0] = i และ dp[0][j] = j ถ้าไม่เติมขอบเหล่านี้ (ปล่อยเป็น 0) คำตอบจะผิดทันที เพราะการเปลี่ยน string ยาว i ให้เป็น empty string ต้อง delete i ครั้ง ไม่ใช่ 0 ครั้ง

ไล่ทีละสเต็ป

table dp ของ word1 = "ros", word2 = "horse" เติมเต็ม (row = ros, column = horse) มุมขวาล่าง = 3:

	ε	h	o	r	s	e
ε	0	1	2	3	4	5
r	1	1	2	2	3	4
o	2	2	1	2	3	4
s	3	3	2	2	2	3 ← คำตอบ

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # base case: เทียบกับสตริงว่าง
    for i in range(m + 1):
        dp[i][0] = i    # ลบ i ตัวให้กลายเป็นสตริงว่าง
    for j in range(n + 1):
        dp[0][j] = j    # แทรก j ตัวจากสตริงว่าง
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:   # ตรงกัน ไม่ต้องแก้
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],       # ลบตัวจาก word1
                    dp[i][j - 1],       # แทรกตัวเข้า word1
                    dp[i - 1][j - 1],   # แทนที่ตัว
                )
    return dp[m][n]

print(min_distance("horse", "ros"))            # 3
print(min_distance("intention", "execution"))  # 5

Output

3
5

ที่ช่อง dp[i][j] ถ้าตัวอักษรท้ายสุดของทั้งสองส่วนตรงกัน (word1[i-1] == word2[j-1]) เราไม่ต้องเสีย edit ที่ตำแหน่งนี้ จึงลอกค่าทแยง dp[i-1][j-1] มาตรง ๆ ถ้าไม่ตรง เราต้อง edit หนึ่งครั้ง แล้วเลือกทางที่ถูกที่สุดจากสามแบบ: delete ตัวท้ายของ word1 (มาจาก dp[i-1][j]), insert ตัวให้ตรง (มาจาก dp[i][j-1]), หรือ replace ตัวท้าย (มาจาก dp[i-1][j-1]) แล้ว +1 สำหรับ edit ครั้งนั้น

base case สำคัญมาก: dp[i][0] = i หมายถึงเปลี่ยน string ยาว i ให้เป็น empty string ต้อง delete i ครั้ง และ dp[0][j] = j หมายถึงสร้าง string ยาว j จาก empty string ต้อง insert j ครั้ง การจับคู่ทิศทางกับความหมาย (บน=delete, ซ้าย=insert, ทแยง=replace) ช่วยให้ไม่งงเวลาเขียนสูตร

Time O(m·n) เติมทุกช่องใน table · Space O(m·n) จาก table dp (ลดเหลือ O(n) ได้ด้วยการเก็บสอง row)

💡 สรุป pattern

Edit Distance เป็นแม่แบบ 2D DP two strings ที่แต่ละช่องเลือกจากเพื่อนบ้านสามทิศตามชนิดของ edit (delete/insert/replace) — จำการจับคู่ ทิศ↔ความหมาย ไว้ แล้วโจทย์ตระกูลนี้ (Delete Operation, One Edit Distance) จะง่ายขึ้นมาก