Hướng dẫn deletion distance python - xóa khoảng cách python

Question

Tôi đã giải quyết vấn đề này tại Pramp và tôi gặp khó khăn trong việc tìm ra thuật toán cho vấn đề này.
Nội dung chính Show

Tổng quan
Dung dịch
Giải pháp 1
Giải pháp 2
Mã ví dụ
Trường hợp kiểm tra
Làm thế nào để Python tính khoảng cách chỉnh sửa?
Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi là bao nhiêu?
Làm thế nào để bạn tìm thấy khoảng cách giữa hai chữ cái trong Python?
Làm thế nào để bạn tìm thấy khoảng cách giữa hai chuỗi?

Nội phân Chính showShow
Mã ví dụ
Làm thế nào để Python tính khoảng cách chỉnh sửa?
Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi là bao nhiêu?
Làm thế nào để bạn tìm thấy khoảng cách giữa hai chữ cái trong Python?
Làm thế nào để bạn tìm thấy khoảng cách giữa hai chuỗi?

Ngược lại, bạn đã thực hiện một công việc rất tốt để đưa ra một giải pháp. Có nhiều cách để cải thiện nó mặc dù.

Như bạn lưu ý, đây chỉ là vấn đề tiếp theo chung dài nhất trong một ngụy trang mỏng. "Khoảng cách xóa" giữa hai chuỗi chỉ là tổng chiều dài của các chuỗi trừ chiều dài của LCS.

Đó là, LCS của

function deletionDistance($str1, $str2) {
  // your code goes here
}

0 (4 ký tự) và

function deletionDistance($str1, $str2) {
  // your code goes here
}

1 (5 ký tự) là

function deletionDistance($str1, $str2) {
  // your code goes here
}

2 (3 ký tự), do đó khoảng cách xóa là (4 + 5) - 2 * 3 = 3.

Do đó, tất cả những gì bạn cần làm để giải quyết vấn đề là có được độ dài của LCS, vì vậy hãy giải quyết vấn đề đó.

Giải pháp của bạn khá tốt nhưng vấn đề chính là thời gian và bộ nhớ của O (Mn) nếu các chuỗi có độ dài m và n. Bạn có thể cải thiện điều này.

Điều đầu tiên cần chú ý là nếu các chuỗi có tiền tố hoặc hậu tố chung thì bạn có thể tự động loại bỏ nó. Đó là, khoảng cách xóa cho

function deletionDistance($str1, $str2) {
  // your code goes here
}

3 và

function deletionDistance($str1, $str2) {
  // your code goes here
}

4 giống như khoảng cách xóa cho

function deletionDistance($str1, $str2) {
  // your code goes here
}

5 và

function deletionDistance($str1, $str2) {
  // your code goes here
}

6. Nó rất rẻ và dễ dàng để xác định xem hai chuỗi có tiền tố và hậu tố chung hay không, và bạn đi từ việc có một mảng với 25*29 phần tử đến một mảng với các yếu tố 5*9, một chiến thắng lớn.It is very cheap and easy to determine if two strings have a common prefix and suffix, and you go from having an array with 25*29 elements to an array with 5*9 elements, a huge win.

Điều tiếp theo cần chú ý là: Bạn xây dựng toàn bộ mảng

function deletionDistance($str1, $str2) {
  // your code goes here
}

7 phía trước, nhưng trong khi bạn đang điền vào mảng,

function deletionDistance($str1, $str2) {
  // your code goes here
}

8 chỉ nhìn vào

function deletionDistance($str1, $str2) {
  // your code goes here
}

9 hoặc

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

0 hoặc

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

1. Vì bạn không bao giờ nhìn vào một dòng mảng cách đó hai, bạn không bao giờ cần nhiều hơn hai dòng! Đó là, bạn có thể:

Phân bổ và tính toán dòng đầu tiên
Phân bổ và tính toán dòng thứ hai được đưa ra dòng đầu tiên
vứt bỏ dòng đầu tiên; Chúng tôi sẽ không bao giờ sử dụng nó nữa
Phân bổ và tính toán dòng thứ ba từ dòng thứ hai
vứt bỏ dòng thứ hai
… và như thế

Bạn vẫn thực hiện các hoạt động O (MN) và bạn vẫn phân bổ tổng số lượng bộ nhớ, nhưng bạn chỉ có một lượng nhỏ trong bộ nhớ cùng một lúc. Nếu các chuỗi lớn, đó là một khoản tiết kiệm đáng kể.

25 tháng 4 năm 2018

Tổng quan

Khoảng cách xóa của hai chuỗi là số lượng ký tự tối thiểu bạn cần xóa trong hai chuỗi để có được cùng một chuỗi. Chẳng hạn, khoảng cách xóa giữa

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

2 và

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

3 là

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

4:

Bằng cách xóa

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

5 và

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

6 trong

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

2 và

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

8 trong

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

3, chúng tôi nhận được chuỗi

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

0 trong cả hai trường hợp.

Chúng ta không thể nhận được cùng một chuỗi từ cả hai chuỗi bằng cách xóa

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

1 chữ cái hoặc ít hơn. Với các chuỗi

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 và

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3, hãy viết một hàm hiệu quả

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

4 trả về khoảng cách xóa giữa chúng. Giải thích cách hoạt động của chức năng của bạn và phân tích độ phức tạp về thời gian và không gian của nó.

Examples:

input:  str1 = "dog", str2 = "frog"
output: 3

input:  str1 = "some", str2 = "some"
output: 0

input:  str1 = "some", str2 = "thing"
output: 9

input:  str1 = "", str2 = ""
output: 0

Constraints:

[Đầu vào] Chuỗi Str1
[đầu vào] Chuỗi str2
[đầu ra] Số nguyên

function deletionDistance($str1, $str2) {
  // your code goes here
}

Gợi ý

Đề xuất bạn bè của bạn để xác định các trường hợp cơ sở trước. Đó là, các trường hợp một trong các chuỗi là chuỗi trống. Trong trường hợp này, khoảng cách xóa chỉ đơn giản là độ dài của chuỗi khác. Sau đó, khuyến khích họ thử các trường hợp có phần giống nhau, chẳng hạn như một chuỗi chứa các ký tự

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

5 hoặc

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

1.

Nếu bạn bè cần hỗ trợ bổ sung, hãy giúp họ bằng cách gợi ý về mối quan hệ đệ quy giữa

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

7 và

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

4 cho một số tiền tố của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 và

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3. Sau khi họ tìm thấy mối quan hệ, bạn có thể đề nghị sử dụng lập trình động.

Nếu bạn bè của bạn vẫn bị mắc kẹt khi tìm kiếm mối quan hệ đệ quy, hướng dẫn họ xem xét hai trường hợp:

Trường hợp 1: Nhân vật cuối cùng trong

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 bằng với ký tự cuối cùng trong

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3. Trong trường hợp đó, người ta có thể cho rằng hai nhân vật này đã bị xóa và nhìn vào các tiền tố mà don lồng bao gồm nhân vật cuối cùng.

Trường hợp 2: Nhân vật cuối cùng trong

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 khác với ký tự cuối cùng trong

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3. Trong trường hợp đó, ít nhất một trong các ký tự phải bị xóa, do đó chúng ta có được phương trình sau:

function deletionDistance($str1, $str2) {
	$cur = range(0, strlen($str1));
	$prev = [];
	for($i=0; $i<=strlen($str2); $i++){
		$prev[$i] = 0;
	}
	
	for($i=0; $i<strlen($str1);$i++){
		$cur = $cur;
		$prev = $prev;
		$cur[0] = $i + 1;
		for($j=0; $j<strlen($str2);$j++){
			$sub = $str1[$i] == $str2[$j] ? 0 : 2;
			$cur[$j+1] = min($prev[$j]+$sub, $cur[$j]+1, $prev[$j+1]+1);
		}
	}
	return $cur[count($cur)-1];
}

5 trong đó

function deletionDistance($str1, $str2) {
	$cur = range(0, strlen($str1));
	$prev = [];
	for($i=0; $i<=strlen($str2); $i++){
		$prev[$i] = 0;
	}
	
	for($i=0; $i<strlen($str1);$i++){
		$cur = $cur;
		$prev = $prev;
		$cur[0] = $i + 1;
		for($j=0; $j<strlen($str2);$j++){
			$sub = $str1[$i] == $str2[$j] ? 0 : 2;
			$cur[$j+1] = min($prev[$j]+$sub, $cur[$j]+1, $prev[$j+1]+1);
		}
	}
	return $cur[count($cur)-1];
}

6 là độ dài của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2,

function deletionDistance($str1, $str2) {
	$cur = range(0, strlen($str1));
	$prev = [];
	for($i=0; $i<=strlen($str2); $i++){
		$prev[$i] = 0;
	}
	
	for($i=0; $i<strlen($str1);$i++){
		$cur = $cur;
		$prev = $prev;
		$cur[0] = $i + 1;
		for($j=0; $j<strlen($str2);$j++){
			$sub = $str1[$i] == $str2[$j] ? 0 : 2;
			$cur[$j+1] = min($prev[$j]+$sub, $cur[$j]+1, $prev[$j+1]+1);
		}
	}
	return $cur[count($cur)-1];
}

8 là độ dài của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3 và

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

0 là khoảng cách xóa giữa

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

1 và

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

2.

Dung dịch

Đặt

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

3 và

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

4 lần lượt là độ dài của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 và

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3. Hãy xem xét chức năng:

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

7 trả về khoảng cách xóa cho tiền tố

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

8 của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 và tiền tố

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

0 của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3. Những gì chúng tôi muốn làm trong giải pháp này, là sử dụng lập trình động để xây dựng một hàm tính toán OPT (Str1Len, Str2Len). Chú ý những điều sau:

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

2

Điều này đúng vì nếu một chuỗi là chuỗi trống, chúng ta không có lựa chọn nào khác ngoài việc xóa tất cả các chữ cái trong chuỗi khác.

Nếu

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

3 và

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

4 thì

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

5

Điều này được giữ vì chúng ta cần xóa ít nhất một trong các chữ cái

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

6 hoặc

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

7 và việc xóa một trong các chữ cái được tính là xóa

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

5 (do đó

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

5 trong công thức). Sau đó, vì chúng tôi đã rời đi với tiền tố

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

0 của STR1 hoặc tiền tố

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

1 của

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3, cần phải lấy mức tối thiểu giữa

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

3 và

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

4. Do đó, chúng tôi có được phương trình

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

5.

Nếu

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

3 và

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

7, thì

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

8

Điều này được tổ chức vì chúng tôi không cần xóa các chữ cái cuối cùng để có được cùng một chuỗi, chúng tôi chỉ cần sử dụng cùng một lần xóa mà chúng tôi sẽ làm cho các tiền tố

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

0 và

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

1.

Giải pháp 1

Sau khi tìm thấy các mối quan hệ ở trên cho

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

7, chúng tôi sử dụng các phương pháp lập trình động để tính toán

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

2, tức là khoảng cách xóa cho hai chuỗi, bằng cách tính

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

7 cho tất cả

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

4,

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

5 và tiết kiệm các giá trị trước đó để sử dụng sau:

Pseudocode:

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

Độ phức tạp về thời gian: Chúng tôi có một vòng lặp lồng nhau thực hiện các bước

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

6 ở mỗi lần lặp, do đó, chúng tôi độ phức tạp thời gian là
$testCase = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0], ["ab", "ba", 2], ]; foreach($testCase as $key=>$case) { $index = $key+1; if ($case[2] != deletionDistance($case[0], $case[1])) { echo "Test case #{$index} failed \n"; } else { echo "Test case #{$index} passed \n"; } }
7 trong đó
$testCase = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0], ["ab", "ba", 2], ]; foreach($testCase as $key=>$case) { $index = $key+1; if ($case[2] != deletionDistance($case[0], $case[1])) { echo "Test case #{$index} failed \n"; } else { echo "Test case #{$index} passed \n"; } }
8 và
$testCase = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0], ["ab", "ba", 2], ]; foreach($testCase as $key=>$case) { $index = $key+1; if ($case[2] != deletionDistance($case[0], $case[1])) { echo "Test case #{$index} failed \n"; } else { echo "Test case #{$index} passed \n"; } }
9 lần lượt là độ dài của
function deletionDistance(str1, str2): # make sure the length of str2 isn't # longer than the length of str1 if (str1.length < str2.length) tmpStr = str1 str1 = str2 str2 = tmpStr str1Len = str1.length str2Len = str2.length prevMemo = new Array(str2Len + 1) currMemo = new Array(str2Len + 1) for i from 0 to str1Len: for j from 0 to str2Len: if (i == 0): currMemo[j] = j else if (j == 0): currMemo[j] = i else if (str1[i-1] == str2[j-1]): currMemo[j] = prevMemo[j-1] else: currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1]) prevMemo = currMemo currMemo = new Array(str2Len + 1); return prevMemo[str2Len]
2 và
function deletionDistance(str1, str2): # make sure the length of str2 isn't # longer than the length of str1 if (str1.length < str2.length) tmpStr = str1 str1 = str2 str2 = tmpStr str1Len = str1.length str2Len = str2.length prevMemo = new Array(str2Len + 1) currMemo = new Array(str2Len + 1) for i from 0 to str1Len: for j from 0 to str2Len: if (i == 0): currMemo[j] = j else if (j == 0): currMemo[j] = i else if (str1[i-1] == str2[j-1]): currMemo[j] = prevMemo[j-1] else: currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1]) prevMemo = currMemo currMemo = new Array(str2Len + 1); return prevMemo[str2Len]
3.: we have a nested loop that executes

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

6 steps at every iteration, thus we the time complexity is

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

7 where

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

8 and

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

9 are the lengths of

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 and

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3, respectively.

Độ phức tạp của không gian: Chúng tôi lưu mọi giá trị của

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

7 trong mảng 2D
testCase = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0], ["ab", "ba", 2], ]; # print(testCase) index = 1; for case in testCase: if(case[2] != deletionDistance(case[0], case[1])): print('#' + str(index) + 'failed \n'); else: print('#' + str(index) + 'passed \n'); index+=1
3 của chúng tôi, chiếm không gian O (N⋅M), trong đó
$testCase = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0], ["ab", "ba", 2], ]; foreach($testCase as $key=>$case) { $index = $key+1; if ($case[2] != deletionDistance($case[0], $case[1])) { echo "Test case #{$index} failed \n"; } else { echo "Test case #{$index} passed \n"; } }
8 và
$testCase = [ ["", "", 0], ["", "hit", 3], ["neat", "", 4], ["heat", "hit", 3], ["hot", "not", 2], ["some", "thing", 9], ["abc", "adbc", 1], ["awesome", "awesome", 0], ["ab", "ba", 2], ]; foreach($testCase as $key=>$case) { $index = $key+1; if ($case[2] != deletionDistance($case[0], $case[1])) { echo "Test case #{$index} failed \n"; } else { echo "Test case #{$index} passed \n"; } }
9 lần lượt là độ dài của
function deletionDistance(str1, str2): # make sure the length of str2 isn't # longer than the length of str1 if (str1.length < str2.length) tmpStr = str1 str1 = str2 str2 = tmpStr str1Len = str1.length str2Len = str2.length prevMemo = new Array(str2Len + 1) currMemo = new Array(str2Len + 1) for i from 0 to str1Len: for j from 0 to str2Len: if (i == 0): currMemo[j] = j else if (j == 0): currMemo[j] = i else if (str1[i-1] == str2[j-1]): currMemo[j] = prevMemo[j-1] else: currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1]) prevMemo = currMemo currMemo = new Array(str2Len + 1); return prevMemo[str2Len]
2 và
function deletionDistance(str1, str2): # make sure the length of str2 isn't # longer than the length of str1 if (str1.length < str2.length) tmpStr = str1 str1 = str2 str2 = tmpStr str1Len = str1.length str2Len = str2.length prevMemo = new Array(str2Len + 1) currMemo = new Array(str2Len + 1) for i from 0 to str1Len: for j from 0 to str2Len: if (i == 0): currMemo[j] = j else if (j == 0): currMemo[j] = i else if (str1[i-1] == str2[j-1]): currMemo[j] = prevMemo[j-1] else: currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1]) prevMemo = currMemo currMemo = new Array(str2Len + 1); return prevMemo[str2Len]
3.: we save every value of

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

7 in our

testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];
# print(testCase)

index = 1;
for case in testCase:
  if(case[2] != deletionDistance(case[0], case[1])):
    print('#' + str(index) + 'failed
\n');
  else:
    print('#' + str(index) + 'passed
\n');
  index+=1

3 2D array, which takes O(N⋅M) space, where

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

8 and

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

9 are the lengths of

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

2 and

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

3, respectively.

Giải pháp 2

Giải pháp ở trên mất không gian

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

7 Vì chúng tôi lưu tất cả các giá trị trước đó, nhưng lưu ý rằng

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

7 chỉ yêu cầu

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

3,

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

4 và

function deletionDistance($str1, $str2) {
  // your code goes here
}

02. Do đó, bằng cách lặp đầu tiên thông qua

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

4, và sau đó cho mỗi

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

8 tính toán

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

5, chúng ta chỉ cần lưu các giá trị cho

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

8 hiện tại và

function deletionDistance(str1, str2):
    str1Len = str1.length
    str2Len = str2.length
    
    # allocate a 2D array with str1Len + 1 rows and str2Len + 1 columns
    memo = new Array(str1Len + 1, str2Len + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                memo[i][j] = j
            else if (j == 0):
                memo[i][j] = i
            else if (str1[i-1] == str2[j-1]):
                memo[i][j] = memo[i-1][j-1]
            else:
                memo[i][j] = 1 + min(memo[i-1][j], memo[i][j-1])

    return memo[str1Len][str2Len]

8 cuối cùng. Điều này sẽ làm giảm không gian cần thiết cho chức năng.

Pseudocode:

function deletionDistance(str1, str2):
    # make sure the length of str2 isn't
    # longer than the length of str1
    if (str1.length < str2.length)
        tmpStr = str1
        str1 = str2
        str2 = tmpStr

    str1Len = str1.length
    str2Len = str2.length
    prevMemo = new Array(str2Len  + 1)
    currMemo = new Array(str2Len  + 1)

    for i from 0 to str1Len:
        for j from 0 to str2Len:
            if (i == 0):
                currMemo[j] = j
            else if (j == 0):
                currMemo[j] = i
            else if (str1[i-1] == str2[j-1]):
                currMemo[j] = prevMemo[j-1]
            else:
                currMemo[j] = 1 + min(prevMemo[j], currMemo[j-1])

        prevMemo = currMemo
        currMemo = new Array(str2Len + 1);  
                                           
    return prevMemo[str2Len]

Độ phức tạp về thời gian: Độ phức tạp thời gian vẫn giữ nguyên, tức là

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

7, vì chúng tôi vẫn chạy một vòng lặp lồng nhau với các lần lặp
function deletionDistance($str1, $str2) { // your code goes here }
09.: the time complexity stays the same, i.e.

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

7, since we still run a nested loop with

function deletionDistance($str1, $str2) {
  // your code goes here
}

09 iterations.

Độ phức tạp không gian:

function deletionDistance($str1, $str2) {
  // your code goes here
}

10, vì chúng ta chỉ cần giữ hai hàng của mảng kép.:

function deletionDistance($str1, $str2) {
  // your code goes here
}

10, as we only need to hold two rows of the double array.

Mã ví dụ

Mã PHP

function deletionDistance($str1, $str2) {
	$cur = range(0, strlen($str1));
	$prev = [];
	for($i=0; $i<=strlen($str2); $i++){
		$prev[$i] = 0;
	}
	
	for($i=0; $i<strlen($str1);$i++){
		$cur = $cur;
		$prev = $prev;
		$cur[0] = $i + 1;
		for($j=0; $j<strlen($str2);$j++){
			$sub = $str1[$i] == $str2[$j] ? 0 : 2;
			$cur[$j+1] = min($prev[$j]+$sub, $cur[$j]+1, $prev[$j+1]+1);
		}
	}
	return $cur[count($cur)-1];
}

Mã Python 1 (làm việc)

def deletionDistance(s1, s2):
  cur = list(range(len(s2) + 1))
  prev = [0] * (len(s2) + 1)
  for i in range(len(s1)):
    cur, prev = prev, cur
    cur[0] = i + 1
    for j in range(len(s2)):
      # Substitution is same as two deletions
      sub = 0 if s1[i] == s2[j] else 2
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)
  return cur[-1]

Mã Python 2 (không hoạt động)

def deletionDistance(s1, s2):
	m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
	for i in range(len(s1)+1):
    	for j in range(len(s2)+1):
	        if i == 0:
	            m[i][j] = sum(bytearray(s2[:j]))
	        elif j == 0:
	            m[i][j] = sum(bytearray(s1[:i]))
	        elif s1[i-1] == s2[j-1]:
	            m[i][j] = m[i-1][j-1]
	        else:
	            m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
	return m[len(s1)][len(s2)]

Mã Python 3 (không hoạt động)

def deletionDistance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

Trường hợp kiểm tra

PHP

$testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];

foreach($testCase as $key=>$case) {
	$index = $key+1;
	if ($case[2] != deletionDistance($case[0], $case[1])) {
		echo "Test case #{$index} failed
\n";
	} else {
		echo "Test case #{$index} passed
\n";
	}
}

Python

testCase = [
	["", "", 0],
	["", "hit", 3],
	["neat", "", 4],
	["heat", "hit", 3],
	["hot", "not", 2],
	["some", "thing", 9],
	["abc", "adbc", 1],
	["awesome", "awesome", 0],
	["ab", "ba", 2],
];
# print(testCase)

index = 1;
for case in testCase:
  if(case[2] != deletionDistance(case[0], case[1])):
    print('#' + str(index) + 'failed
\n');
  else:
    print('#' + str(index) + 'passed
\n');
  index+=1

https://stackoverflow.com/questions/44490091/deletion-distance-between-2-strings https://stackoverflow.com/questions/41275345/deletion-distance-between-words

Làm thế nào để Python tính khoảng cách chỉnh sửa?

Khoảng cách chỉnh sửa giữa hai chuỗi đề cập đến số lượng tối thiểu của các lần chèn, xóa và thay thế ký tự cần thiết để thay đổi một chuỗi sang chuỗi kia. Ví dụ: khoảng cách chỉnh sửa giữa "mèo con" và "ngồi" là ba: thay thế "k" cho "s", thay thế "e" cho "i", và nối "g".substitute the "k" for "s", substitute the "e" for "i", and append a "g".

Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi là bao nhiêu?

Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi STR1 và STR2 được định nghĩa là số lượng hoạt động chèn/xóa/thay thế tối thiểu cần thiết để biến STR1 thành str2. Ví dụ: nếu str1 = "ab", str2 = "abc" sau đó tạo một thao tác chèn của ký tự 'C' trên str1 biến đổi str1 thành str2.the minimum number of insert/delete/substitute operations required to transform str1 into str2. For example if str1 = "ab", str2 = "abc" then making an insert operation of character 'c' on str1 transforms str1 into str2.

Làm thế nào để bạn tìm thấy khoảng cách giữa hai chữ cái trong Python?

Khoảng cách giữa hai chữ cái là sự khác biệt giữa các vị trí của chúng trong bảng chữ cái. Ví dụ: dist (c, e) = dist (e, c) = 2. dist (a, z) = dist (z, a) = 25.difference between their positions in the alphabet. for example: dist(c, e) = dist(e, c) = 2. dist(a, z) = dist(z, a) = 25.

Làm thế nào để bạn tìm thấy khoảng cách giữa hai chuỗi?

Có một số cách để đo khoảng cách giữa hai chuỗi. Điều đơn giản nhất là sử dụng khoảng cách Hamming để tìm số lượng không khớp giữa hai chuỗi. Tuy nhiên, hai chuỗi phải có cùng chiều dài.use hamming distance to find the number of mismatch between two strings. However, the two strings must have the same length.

programming python Edit distance Python Euclidean distance Python Levenshtein distance Python

Hướng dẫn deletion distance python - xóa khoảng cách python

Tổng quan

Gợi ý

Dung dịch

Giải pháp 1

Giải pháp 2

Mã ví dụ

Trường hợp kiểm tra

Làm thế nào để Python tính khoảng cách chỉnh sửa?

Khoảng cách chỉnh sửa tối thiểu giữa hai chuỗi là bao nhiêu?

Làm thế nào để bạn tìm thấy khoảng cách giữa hai chữ cái trong Python?

Làm thế nào để bạn tìm thấy khoảng cách giữa hai chuỗi?

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội