Edit Distance

Q: Khoảng cách chỉnh sửa có thể được giải bằng một mảng duy nhất không?

Đúng vậy. Điền vào một mảng row ngay tại chỗ, từ trái sang phải. Trước khi ghi đè row[j] , nó vẫn giữ giá trị từ hàng phía trên, còn row[j-1] đã giữ giá trị của hàng hiện tại. Chỉ giá trị trên đường chéo bị mất, nên hãy lưu giá trị cũ của row[j] vào một biến và dùng nó làm giá trị trên đường chéo cho j + 1 .

KhóQuy hoạch động

+10

Bạn nhận được hai từ, word1 và word2. Mỗi lần chỉnh sửa sẽ thay đổi word1 theo một trong ba cách: chèn một chữ cái vào bất kỳ vị trí nào, xóa một chữ cái hoặc thay một chữ cái bằng một chữ cái khác. Hãy trả về số lần chỉnh sửa ít nhất để biến word1 thành word2.

Hàm

minDistance(word1: string, word2: string) → integer

word1string: từ bạn chỉnh sửa
word2string: từ cần đạt đến
Trả vềinteger: số lần chèn, xóa và thay thế ít nhất để biến word1 thành word2

Ràng buộc

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Cả hai từ chỉ chứa các chữ cái tiếng Anh viết thường.

Ví dụ

Đầu vào: word1 = "spot"word2 = "stop"
Đầu ra: 2
Giải thích: Thay p bằng t và t bằng p: spot trở thành stot, rồi stop. Một lần chỉnh sửa là chưa đủ, vì hai từ khác nhau ở hai vị trí, còn thêm hoặc xóa một ký tự sẽ làm thay đổi độ dài.

Đầu vào: word1 = "garden"word2 = "ardent"
Đầu ra: 2
Giải thích: Xóa chữ g để được arden, rồi thêm chữ t vào cuối để được ardent. Thay từng chữ cái sẽ tốn 6, vì hai từ khác nhau ở mọi vị trí.

Đầu vào: word1 = "rain"word2 = "shine"
Đầu ra: 3
Giải thích: Thay r bằng s và a bằng h, rồi chèn e. Hai lần chỉnh sửa không thể thực hiện được: r và a không có trong shine, nên mỗi lần chỉnh sửa cần giữ nguyên độ dài, và từ đó vẫn phải dài thêm một ký tự.

Câu hỏi mở rộng

Bạn cũng có thể trả về một danh sách các chỉnh sửa ngắn nhất cùng với số lượng của chúng không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Các chỉnh sửa có tác động qua lại: garden và ardent khác nhau ở cả sáu vị trí, nhưng chỉ cần hai chỉnh sửa. Vì vậy, hãy xét chữ cái cuối cùng của mỗi từ. Hoặc hai chữ cái giống nhau, hoặc một trong ba chỉnh sửa khiến chúng giống nhau, và mỗi lựa chọn đều để lại cùng một bài toán với các tiền tố ngắn hơn. Một bảng giải quyết mỗi cặp tiền tố đúng một lần.

Thử cả ba chỉnh sửa với đệ quy

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Gọi edits(i, j) là số thao tác chỉnh sửa ít nhất để biến hậu tố word1[i:] thành word2[j:]. Nếu chữ cái đầu tiên giống nhau, hãy giữ nguyên chúng và tăng cả hai chỉ số: chỉnh sửa một chữ cái vốn đã khớp không bao giờ có ích. Nếu không, lấy 1 cộng với số nhỏ nhất trong ba lời gọi: thay thế thì tăng cả hai chỉ số, xóa word1[i] thì tăng i, còn chèn word2[j] thì tăng j. Khi một từ đã hết, mỗi chữ cái còn lại trong từ kia cần một thao tác chỉnh sửa.

Mỗi chỗ không khớp bắt đầu ba lời gọi: hai từ dài 15 chữ cái không có chữ cái nào chung cần khoảng 6.7 × 10^10 lời gọi. Tuy nhiên, chỉ có (n+1) × (m+1) cặp khác nhau (i, j), nên gần như mọi lời gọi đều lặp lại một lời gọi trước đó.

Thuật toán

Nếu i vượt quá cuối word1, trả về m - j; nếu j vượt quá cuối word2, trả về n - i.
Nếu word1[i] == word2[j], trả về edits(i+1, j+1).
Nếu không, trả về 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)).
Đáp án là edits(0, 0).

def minDistance(word1, word2):
    n, m = len(word1), len(word2)

    def edits(i, j):
        # Fewest edits to turn word1[i:] into word2[j:]
        if i == n:
            return m - j  # insert the rest of word2
        if j == m:
            return n - i  # delete the rest of word1
        if word1[i] == word2[j]:
            return edits(i + 1, j + 1)
        return 1 + min(edits(i + 1, j + 1),  # replace word1[i] with word2[j]
                       edits(i + 1, j),      # delete word1[i]
                       edits(i, j + 1))      # insert word2[j]

    return edits(0, 0)

Điền bảng tiền tố

Ý tưởng

Gọi dp[i][j] là số phép sửa ít nhất để biến i chữ cái đầu tiên của word1 thành j chữ cái đầu tiên của word2. Nếu word1[i-1] bằng word2[j-1], ta sao chép ô chéo dp[i-1][j-1]. Nếu không, ta trả thêm 1 cộng với giá trị nhỏ nhất trong các ô lân cận: ô chéo tương ứng với phép thay thế, ô phía trên tương ứng với phép xóa word1[i-1], ô bên trái tương ứng với phép chèn word2[j-1]. Hàng và cột cơ sở không phải là các số 0: xóa i chữ cái để thành chuỗi rỗng cần i phép xóa, nên dp[i][0] = i, tương tự dp[0][j] = j.

Với spot thành stop, hàng cuối cùng là [4, 3, 2, 2, 2]. Ô cuối cùng so sánh t với p; ô chéo (spo thành sto) có giá trị 1, còn các ô lân cận khác có giá trị 2, nên đáp án là 1 + 1 = 2. Hai từ dài 500 chữ cái cần điền 2.5 × 10^5 ô, mỗi ô được tính trong thời gian hằng số.

Thuật toán

Tạo dp với (n+1) × (m+1) ô, dp[i][0] = i và dp[0][j] = j.
Với i từ 1 đến n và j từ 1 đến m: nếu word1[i-1] == word2[j-1], đặt dp[i][j] = dp[i-1][j-1].
Nếu không, đặt dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Trả về dp[n][m].

def minDistance(word1, word2):
    n, m = len(word1), len(word2)
    # dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j  # insert all j letters
    for i in range(1, n + 1):
        for j in range(1, m + 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 - 1],  # replace
                                   dp[i - 1][j],      # delete word1[i-1]
                                   dp[i][j - 1])      # insert word2[j-1]
    return dp[n][m]

Chỉ giữ lại hai hàng

Ý tưởng

Hàng i chỉ đọc hàng i-1 và các ô bên trái trong chính hàng đó, nên chỉ cần hai mảng: prev cho hàng đã hoàn thành và cur cho hàng đang được điền. Đường chéo là prev[j-1], phía trên là prev[j] và bên trái là cur[j-1]. Cột cơ sở giờ nằm ở phần tử đầu tiên của mỗi hàng, nên hãy đặt cur[0] = i trước khi điền hàng i.

Chuyển word2 thành word1 cần cùng số lần chỉnh sửa, vì phép chèn và phép xóa có thể hoán đổi cho nhau. Hãy đổi chỗ hai từ để các hàng chạy theo từ ngắn hơn: min(n, m) + 1 số cho mỗi hàng thay vì một bảng có tối đa 251,001 ô, với cùng khối lượng công việc O(n × m).

Thuật toán

Nếu word2 dài hơn word1, hãy đổi chỗ chúng.
Đặt prev = [0, 1, ..., m].
Với mỗi i từ 1 đến n, đặt cur[0] = i và điền cur[1..m] theo quy tắc của bảng, lấy giá trị đường chéo và phía trên từ prev, còn giá trị bên trái từ cur. Sau đó đổi chỗ prev và cur.
Trả về prev[m].

def minDistance(word1, word2):
    if len(word2) > len(word1):
        word1, word2 = word2, word1  # the rows run along the shorter word
    m = len(word2)
    # prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
    prev = list(range(m + 1))
    for i in range(1, len(word1) + 1):
        cur = [i] + [0] * m  # i letters into an empty prefix: delete them all
        for j in range(1, m + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],  # replace
                                 prev[j],      # delete word1[i-1]
                                 cur[j - 1])   # insert word2[j-1]
        prev = cur
    return prev[m]

Lỗi thường gặp và trường hợp biên

Điền số 0 vào hàng 0 và cột 0 như trong bài toán dãy con chung dài nhất. Biến abc thành tiền tố rỗng cần 3 lần xóa, không phải 0.
Quên cur[0] = i trong phiên bản hai hàng. Phần tử đầu tiên giữ giá trị từ hai hàng trước đó, khiến mọi ô phía sau đều sai.
Tính chi phí chỉnh sửa khi hai ký tự trùng nhau. Nếu dùng 1 + min(...) khi các chữ cái giống nhau, biến a thành a sẽ tốn 1.
Đọc phần tử bên trái từ prev thay vì cur. Phần tử bên trái là thao tác chèn word2[j-1] ở hàng hiện tại.
Dùng đệ quy có ghi nhớ trong Python với các từ dài 500 ký tự. Các lệnh gọi có độ sâu lên đến 1000, vượt quá giới hạn đệ quy mặc định.

Câu hỏi thường gặp3

Độ phức tạp thời gian của khoảng cách chỉnh sửa là bao nhiêu?

Lời giải dùng bảng điền một ô cho mỗi cặp tiền tố trong thời gian hằng số: thời gian O(n × m) với độ dài n và m. Lời giải dùng O(n × m) bộ nhớ cho toàn bộ bảng, hoặc O(min(n, m)) bộ nhớ khi dùng hai hàng. Đệ quy thông thường không dùng bảng có độ phức tạp theo hàm mũ.

Khoảng cách chỉnh sửa có giống khoảng cách Levenshtein không?

Phiên bản này là khoảng cách Levenshtein: mỗi thao tác chèn, xóa và thay thế đều có chi phí bằng một. Khoảng cách chỉnh sửa là tên gọi chung. Chỉ dùng thao tác chèn và xóa thì ta có n + m - 2 × LCS, chỉ dùng thao tác thay thế khi hai chuỗi có độ dài bằng nhau thì ta có khoảng cách Hamming, còn thêm thao tác đổi chỗ hai chữ cái liền kề thì ta có phiên bản Damerau.

Khoảng cách chỉnh sửa có thể được giải bằng một mảng duy nhất không?

Đúng vậy. Điền vào một mảng row ngay tại chỗ, từ trái sang phải. Trước khi ghi đè row[j], nó vẫn giữ giá trị từ hàng phía trên, còn row[j-1] đã giữ giá trị của hàng hiện tại. Chỉ giá trị trên đường chéo bị mất, nên hãy lưu giá trị cũ của row[j] vào một biến và dùng nó làm giá trị trên đường chéo cho j + 1.

def minDistance(word1, word2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

word1 = "spot"
word2 = "stop"

Đầu ra mong đợi

Edit Distance

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử cả ba chỉnh sửa với đệ quy

Điền bảng tiền tố

Chỉ giữ lại hai hàng

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự