Edit Distance and Dynamic Programming

Edit Distance and Dynamic Programming

Edit Distance

This is a medium-to-hard problem on Leetcode. Edit distance is often used when computing text similarity. It refers to the minimum number of edit operations required to turn one string into another. Generally speaking, the smaller the edit distance, the more similar the two texts are. The edit operations fall into three main kinds:

1. Insertion: insert a character into a string
2. Deletion: delete a character from a string
3. Substitution: replace a character in a string with another character

Examples

1. Turning batyu into beatyu requires inserting the character e, which is one edit operation
2. Turning beatyu into beaty requires deleting the character u, one operation
3. Turning apple into appel requires two operations

dhsfka fdshakjfhl

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    if m == 0:
        return n
    if n == 0:
        return m

    # Build an (m+1)*(n+1) table, with s1 horizontal and s2 vertical
    edit = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        edit[i][0] = i
    for j in range(1, n + 1):
        edit[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                diff = 0
            else:
                diff = 1
            edit[i][j] = min(edit[i - 1][j - 1] + diff, edit[i - 1][j] + 1, edit[i][j - 1] + 1)

    return edit[m][n]

print(edit_distance('好的伤口恢复了', '浑善达克距离罚款'))