findingsea's Studio.

Edit Distance@LeetCode

LeetCode
Word count: 254 / Reading time: 1 min
2015/04/12 Share

Edit Distance

典型的动态规划题目。维护一个二维数组dis[][]，dis[i][j]表示：word1的前i个元素与word2的前j个元素的edit distance值。递推关系为：

  • 当word1[i] == word2[j]，dis[i][j] = dis[i][j - 1]。
  • 当word[i] != word2[j]，dis[i][j] = min(dis[i - 1][j - 1], dis[i] [j - 1], dis[i - 1][j]) + 1。

解释一下第二种情况下的递推公式：

  • dis[i][j] = dis[i - 1][j - 1] + 1意味着替换字符
  • dis[i][j] = dis[i - 1][j] + 1意味着删除字符
  • dis[i][j] = dis[i][j - 1] + 1意味着插入字符

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int minDistance(String word1, String word2) {
        int[] result = new int[word1.length() + 1];
        for (int i = 0; i < result.length; i++)
            result[i] = i;
        for (int i = 0; i < word2.length(); i++) {
            int[] newResult = new int[result.length];
            newResult[0] = i + 1;
            for (int j = 0; j < word1.length(); j++) {
                if (word1.charAt(j) == word2.charAt(i)) {
                    newResult[j + 1] = result[j];
                } else {
                    newResult[j + 1]  = Math.min(result[j], Math.min(result[j + 1], newResult[j])) + 1;
                }
            }
            result = newResult;
        }
        return result[result.length - 1];
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/04/12/edit-distance-at-leetcode/

发表日期: April 12th 2015, 2:47:00 pm

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Edit Distance
Total : 100
2020
2019
2018
2017
2015
2014
2013
Octopress GitHub Python Django 吐槽 Reading ACM 项目总结 JavaScript 日志 Java LeetCode Interview Algorithm Life Windows ffmpeg life Go c++ essay review