Thuật toán Ứng dụng — DP, String, Big Data & hơn nữa/Mini-challenge — Edit Distance: khoảng cách sửa giữa 2 chuỗi
8/66
Bài 8 / 66~30 phútQuyết định dưới constraint — DP, Greedy, BacktrackingMiễn phí… lượt xem

Mini-challenge — Edit Distance: khoảng cách sửa giữa 2 chuỗi

Implement editDistance(s, t) trả số phép chèn/xoá/thay tối thiểu — DP 2D cổ điển nằm sau autocorrect, spell-check, diff tool, và bioinformatics sequence alignment.

Bạn đang build tính năng autocorrect cho bàn phím tiếng Việt: người dùng gõ "hocj" — phần mềm cần tìm từ trong từ điển gần nhất để gợi ý. "Gần nhất" ở đây không phải độ dài hay số ký tự chung, mà là số phép sửa tối thiểu để biến chuỗi gõ sai thành chuỗi đúng.

Cùng pattern này xuất hiện trong:

  • git diff / Unix diff — khoảng cách giữa 2 phiên bản file để tìm minimal edit.
  • Spell-check (hunspell, aspell) — xếp hạng gợi ý theo edit distance.
  • Bioinformatics — so sánh chuỗi DNA/protein, tìm đột biến tối thiểu.
  • LeetCode 72. Edit Distance — bài DP cổ điển, hard difficulty.

Ba phép sửa được định nghĩa:

PhépMô tảVí dụ "cat" → "car"
InsertChèn 1 ký tự vào"ca" → "car"
DeleteXoá 1 ký tự"cats" → "cat"
ReplaceThay 1 ký tự"cat" → "car"

Mỗi phép có cost 1. Bài toán: tìm tổng cost nhỏ nhất.

Dành 20–25 phút tự implement trước khi xem gợi ý.

⁂

🎯 Đề bài

Viết hàm editDistance(s, t) với API:

  • Input: 2 chuỗi s và t, mỗi chuỗi độ dài tối đa 1000 ký tự.
  • Output: số nguyên — số phép insert/delete/replace tối thiểu để biến s thành t.
  • Mỗi phép cost 1.

📋 Test cases

stExpectedGiải thích
"horse""ros"3horse → rorse (replace h→r) → rose (delete r) → ros (delete e)
"intention""execution"55 phép tối thiểu
"""abc"33 insert
"abc"""33 delete
"abc""abc"0Giống hệt
"a""b"11 replace
⁂

📦 Starter pseudocode

editDistance(s, t):
    n <- s.length
    m <- t.length
    -- TODO: xây dp[0..n][0..m]
    -- dp[i][j] = edit distance giữa s[0..i-1] và t[0..j-1]
    return dp[n][m]
⁂

💡 Gợi ý

💡 Stage 1 — Định nghĩa subproblem (đọc khi chưa biết bắt đầu từ đâu)

Gọi dp[i][j] = edit distance giữa tiền tố s[0..i-1] và tiền tố t[0..j-1].

Trường hợp cơ sở:

  • dp[0][j] = j — biến chuỗi rỗng thành t[0..j-1] cần j lần insert.
  • dp[i][0] = i — biến s[0..i-1] thành chuỗi rỗng cần i lần delete.

Mục tiêu: tính dp[n][m].

Gợi ý cách hiểu: dp[i][j] trả lời câu hỏi "Tốn bao nhiêu phép nếu chỉ xét i ký tự đầu của s và j ký tự đầu của t?"

💡 Stage 2 — Transition (đọc khi đã hiểu subproblem nhưng chưa ra công thức)

Với mỗi cặp (i, j), xét ký tự s[i-1] và t[j-1]:

Trường hợp 1 — ký tự bằng nhau (s[i-1] = t[j-1]):

Không cần sửa ký tự này. dp[i][j] = dp[i-1][j-1].

Trường hợp 2 — ký tự khác nhau, chọn phép cost nhỏ nhất trong 3 phép:

PhépÝ nghĩaCost
Replace s[i-1] thành t[j-1]Đã xử lý cả 2 ký tựdp[i-1][j-1] + 1
Delete s[i-1]Chưa xử lý t[j-1]dp[i-1][j] + 1
Insert t[j-1] vào cuối sChưa xử lý s[i-1]dp[i][j-1] + 1

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

💡 Stage 3 — Tối ưu bộ nhớ (đọc sau khi đã có O(n*m) chạy đúng)

Mảng dp[n+1][m+1] dùng O(n×m) space. Nhưng transition chỉ cần hàng trước (dp[i-1][...]) và hàng hiện tại — nên có thể tối ưu xuống O(min(n, m)) bằng 2 mảng 1D.

Nếu n > m, swap s và t trước để hàng ngắn hơn là "cột", tiết kiệm bộ nhớ tối đa.

⁂

✅ Lời giải

✅ Lời giải — xem sau khi đã tự làm

Phần 1 — DP 2D chuẩn

editDistance(s, t):
    n <- s.length
    m <- t.length

    -- Khởi tạo bảng dp kích thước (n+1) × (m+1)
    dp[0..n][0..m] <- 0

    -- Base case: biến chuỗi rỗng thành t[0..j-1] hoặc ngược lại
    for i from 0 to n:
        dp[i][0] <- i     -- xoá hết i ký tự của s
    for j from 0 to m:
        dp[0][j] <- j     -- chèn j ký tự của t vào chuỗi rỗng

    -- Fill bảng theo thứ tự i tăng dần, j tăng dần
    for i from 1 to n:
        for j from 1 to m:
            if s[i-1] = t[j-1]:
                dp[i][j] <- dp[i-1][j-1]       -- ký tự khớp, không tốn phép
            else:
                replace <- dp[i-1][j-1] + 1    -- thay ký tự
                delete  <- dp[i-1][j]   + 1    -- xoá s[i-1]
                insert  <- dp[i][j-1]   + 1    -- chèn t[j-1]
                dp[i][j] <- min(replace, delete, insert)

    return dp[n][m]

-- Time: O(n*m)  Space: O(n*m)

Trace s = "horse", t = "ros" (n=5, m=3):

""ros
""0123
h1123
o2212
r3222
s4332
e5443

dp[5][3] = 3 — đúng với expected.

Phần 2 — Space-optimize xuống 2 hàng

editDistanceOptimized(s, t):
    -- Đảm bảo t là chuỗi ngắn hơn để tiết kiệm bộ nhớ
    if s.length < t.length:
        swap(s, t)

    n <- s.length
    m <- t.length

    prev[0..m] <- [0, 1, 2, ..., m]   -- dp[i-1][...]
    curr[0..m] <- 0                    -- dp[i][...]

    for i from 1 to n:
        curr[0] <- i                   -- base case: xoá i ký tự
        for j from 1 to m:
            if s[i-1] = t[j-1]:
                curr[j] <- prev[j-1]
            else:
                curr[j] <- min(prev[j-1], prev[j], curr[j-1]) + 1
        swap(prev, curr)               -- hàng curr trở thành prev cho vòng sau

    return prev[m]

-- Time: O(n*m)  Space: O(min(n,m))

Phần 3 — Reconstruct các phép cụ thể

Khi cần biết chính xác những phép nào (autocorrect hiển thị từng bước sửa), trace ngược từ dp[n][m]:

reconstructOps(dp, s, t):
    ops <- []    -- danh sách phép: ("replace", i, c), ("delete", i), ("insert", i, c)
    i <- s.length
    j <- t.length

    while i > 0 hoặc j > 0:
        if i > 0 và j > 0 và s[i-1] = t[j-1]:
            i <- i - 1
            j <- j - 1          -- match, không phép nào
        else if i > 0 và j > 0 và dp[i][j] = dp[i-1][j-1] + 1:
            ops.prepend(("replace", i-1, t[j-1]))
            i <- i - 1
            j <- j - 1
        else if i > 0 và dp[i][j] = dp[i-1][j] + 1:
            ops.prepend(("delete", i-1))
            i <- i - 1
        else:
            ops.prepend(("insert", i, t[j-1]))
            j <- j - 1

    return ops

-- Time: O(n+m) sau khi có bảng dp  Space: O(n+m) cho ops
⁂

📊 Phân tích độ phức tạp

VariantTimeSpace
DP 2D chuẩnO(n×m)O(n×m)
Space-optimize 2 hàngO(n×m)O(min(n,m))
Reconstruct opsO(n×m) + O(n+m) traceO(n×m) cho bảng

Với n = m = 1000, DP 2D cần 1 triệu ô — khoảng 4 MB (int 4 byte), chấp nhận được cho thực tế.

Tại sao không thể tốt hơn O(n×m)? Mọi subproblem dp[i][j] đều cần thiết — không subproblem nào có thể bỏ qua mà không mất thông tin. Đây là lower bound của bài toán edit distance chính xác. (Có thuật toán xấp xỉ nhanh hơn, nhưng không cho kết quả chính xác.)

graph TD
    A["dp[i-1][j-1]<br/>Cả 2 ký tự đã xử lý"] -- "khớp: +0<br/>khác: replace +1" --> D["dp[i][j]"]
    B["dp[i-1][j]<br/>Chỉ s[i-1] đã xử lý"] -- "delete s[i-1]: +1" --> D
    C["dp[i][j-1]<br/>Chỉ t[j-1] đã xử lý"] -- "insert t[j-1]: +1" --> D
⁂

✨ Điều bạn vừa làm được

  • Xây bảng DP 2D với dp[i][j] là edit distance của tiền tố s[0..i-1] và t[0..j-1] — pattern "prefix DP" cổ điển.
  • Áp transition 3 phép (replace/delete/insert), hiểu tại sao mỗi lựa chọn map sang ô nào trong bảng.
  • Space-optimize từ O(n×m) xuống O(min(n,m)) bằng 2 hàng cuộn — technique áp dụng cho mọi DP chỉ cần hàng liền trước.
  • Reconstruct đường đi thực tế từ bảng DP — pattern dùng trong git diff để hiển thị từng dòng thay đổi.
  • Nhận ra edit distance là cơ sở của autocorrect, diff tool, và sequence alignment trong bioinformatics.
⁂

Bài tiếp theo: Case study: LCS trong git diff & Huffman trong gzip

Bài này có giúp bạn hiểu bản chất không?

Hỏi đáp về bài này

Chưa có câu hỏi

Đặt câu hỏi

Có gì chưa rõ trong bài? Đặt câu hỏi đầu tiên — câu trả lời từ cộng đồng giúp bạn (và người sau).

Đặt câu hỏi đầu tiên
← Bài trước

Backtracking và cắt tỉa — Permutations, N-Queens, pruning

Bài tiếp

Case Study: LCS trong git diff & Huffman trong gzip