Edit Distance, Leetcode 解题笔记

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

这是一道经典算法题,像这种找最短路径的问题一般要考虑动态规范的策略,但是这题如果没见过还真不好想到它的思路,所以可以把这道题的算法记在脑子里。

关键点就是我们要定义一个二维数组,这个数组中A[i][j]的值表示的含义是word1的第前i个字符到word2的第前j个字符的最短Edit Distance。
如此一来,我们可以得出初始条件:A[i][0] = i, A[0][j] = j。
最后要求的结果则是A[m][n], m和n分别是word1和word2的长度。

public class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i = 0; i < word1.length()+1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j < word2.length()+1; j++){
            dp[0][j] = j;
        }
        for(int i = 0; i < word1.length(); i++){
            char c1 = word1.charAt(i);
            for(int j = 0; j < word2.length(); j++){
                char c2 = word2.charAt(j);
                if(c1 == c2){
                    dp[i+1][j+1] = dp[i][j];
                }
                else{
                    int insert = dp[i][j+1] + 1;
                    int delete = dp[i+1][j] + 1;
                    int replace = dp[i][j] + 1;
                    dp[i+1][j+1] = Math.min(Math.min(insert, delete), replace);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s