编辑距离

什么是编辑距离

编辑距离是指，将一个字符串转化成另一个字符串，需要的最少编辑次数。编辑包括增加一个字符、删除一个字符、替换一个字符。

编辑距离越大，说明两个字符串的相似程度越小；反之，编辑距离越小，说明两个字符串的相似程度越大。如果两个字符串完全相同，编辑距离就是0。

编辑距离的计算方式

• 莱文斯坦距离

  允许增加、删除、替换字符这三个编辑操作。

  莱文斯坦距离的大小，表示两个字符串差异的大小。

  比如：mitcmu和mtacnu的莱文斯坦距离是3。

• 最长公共子串长度

  允许增加、删除字符这两个编辑操作。

  最长公共子串的大小，表示两个字符串相似程度的大小。

  比如：mitcmu和mtacnu的公共最长公共子串长度是4。

莱文斯坦距离

回溯法

递归考察a[i]与b[j]，如果不匹配，可以有多种处理方式：

• 删除a[i]，然后递归考察a[i+1]和b[j]

• 删除b[j]，然后考察a[i]和b[j+1]

• 在a[i]前添加一个跟b[j]相同的字符，然后考察a[i]和b[j+1]

• 在b[j]前添加一个跟a[i]相同的字符，然后递归考察a[i+1]和b[j]

• 将a[i]替换成b[j]，或者将b[j]替换成a[i]，然后考察a[i+1]和b[j+1]

如果a[i]与b[j]匹配，则考察a[i+1]和b[j+1]

回溯解法代码：

func lwstBT(str1, str2 string) int {
    minDist := len(str1)
    if len(str2) > len(str1) {
        minDist = len(str2)
    }
    return helper(str1, str2, 0, 0, 0, minDist)
}

func helper(str1, str2 string, i, j, curDist, minDist int) int {
    l1, l2 := len(str1), len(str2)
    if i == l1 || j == l2 {
        if i < l1 {
            curDist += (l1 - i)
        }
        if j < l2 {
            curDist += (l2 - j)
        }
        if curDist < minDist {
            minDist = curDist
        }
        return minDist
    }

    if str1[i] == str2[j] {
        return helper(str1, str2, i+1, j+1, curDist, minDist)
    }
    // 删除str1[i] 或者str2[j]前添加字符
    minDist = helper(str1, str2, i+1, j, curDist+1, minDist)
    // 删除str2[j] 或者str1[i]前添加字符
    minDist = helper(str1, str2, i, j+1, curDist+1, minDist)
    // 替换str1[i]或者str2[j] 是
    minDist = helper(str1, str2, i+1, j+1, curDist+1, minDist)
    return minDist
}

使用回溯解法，会产生很多重复状态，符合动态规划“重复子问题”的要求，所以可以使用“动态规划”来解题 。

动态规划

使用min_edist表示某一阶段决策结束之后，获得的最少编辑次数。对于a[i]和b[j]，我们可以知道：

# 如果a[i] != b[j]
min_edist(i, j) = min(
    min_edist(i-1, j) + 1,
    min_edist(i, j-1) + 1,
    min_edist(i-1, j-1) + 1,
)

# 如果a[i] == b[j]
min_edist(i, j) = min(
    min_edist(i-1, j),
    min_edist(i, j-1),
    min_edist(i-1, j-1),
)

将上述状态转移方程翻译成代码，可得：

func lwstBT(str1, str2 string) int {
    dp := make([][]int, len(str1))
    for i := range dp {
        dp[i] = make([]int, len(str2))
    }
    if str1[0] == str2[0] {
        dp[0][0] = 0
    } else {
        dp[0][0] = 1
    }
    for i := 1; i < len(str2); i++ {
        if str1[0] == str2[i] {
            dp[0][i] = i
        } else {
            dp[0][i] = dp[0][i-1] + 1
        }
    }
    for i := 1; i < len(str1); i++ {
        if str2[0] == str1[i] {
            dp[i][0] = i
        } else {
            dp[i][0] = dp[i-1][0] + 1
        }
    }
    for i := 1; i < len(str1); i++ {
        for j := 1; j < len(str2); j++ {
            if str1[i] == str2[j] {
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
            } else {
                dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)
            }
        }
    }
    return dp[len(str1)-1][len(str2)-1]
}

func min(x, y, z int) int {
    if x > y {
        if y > z {
            return z
        }
        return y
    }
    if x > z {
        return z
    }
    return x
}

最长公共子串长度

回溯思路

考察a[i]和b[j]。

• 如果匹配，将公共子串长度+1，然后考察a[i+1]和b[j+1]

• 如果不匹配，最长公共子串长度不变。这时，可删除a[i]，或者在b[j]前加一个字符，然后考察a[i+1]和b[j]；还可以删除b[j]，或者在a[i]前加一个字符b[j]，然后考察a[i]和b[j+1]

动态规划思想

使用max_lcs，表示当前决策阶段的最长公共子串长度。

# 如果a[i] == b[j]
max_lcs(i, j) = max(
    max_lcs(i-1, j-1)+1, max_lcs(i-1, j)+1, max_lcs(i, j-1)+1,
)

# 如果a[i] != b[j]
max_lcs(i, j) = max(
    max_lcs(i, j-1), max_lcs(i-1, j), max_lcs(i-1, j-1),
)

将动态转移方程翻译成代码：

func lcs(str1, str2 string) int {
    dp := make([][]int, len(str1))
    for i := range dp {
        dp[i] = make([]int, len(str2))
    }

    if str1[0] == str2[0] {
        dp[0][0] = 1
    } else {
        dp[0][0] = 0
    }
    for i := 1; i < len(str2); i++ {
        if str1[0] == str2[i] {
            dp[0][i] = 1
        } else {
            dp[0][i] = dp[0][i-1]
        }
    }
    for i := 1; i < len(str1); i++ {
        if str2[0] == str1[i] {
            dp[i][0] = 1
        } else {
            dp[i][0] = dp[i-1][0]
        }
    }
    for i := 1; i < len(str1); i++ {
        for j := 1; j < len(str2); j++ {
            if str1[i] == str2[j] {
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
            } else {
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[len(str1)-1][len(str2)-1]
}

func max(x, y, z int) int {
    max := -1
    if x > max {
        max = x
    }
    if y > max {
        max = y
    }
    if z > max {
        max = z
    }
    return max
}