LintCode 119. Edit Distance 原创Java参考解答

LintCode 119. Edit Distance 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/edit-distance/

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:

  • Insert a character
  • Delete a character
  • Replace a character

Example

Given word1 = "mart" and word2 = "karma", return 3.

解题思路

题目是求从word1变成word2的最小步骤数。

动态规划的代表题之一。动态规划方程f[i][j]表示从word1第i位置到word2第j位置的最小步骤数。

  • 初始化,word1第i位置到word2第0位置需要i步骤(删除i次)。
  • 初始化,word1第0位置到word2第j位置需要j步骤(插入j次)。
  • 其他位置上,f[i][j]是word1第i – 1位置到word2第j位置 + 1(添加1次),word1第i位置到word2第j – 1位置 + 1(删除1次),word1第i – 1位置到word2第j – 1位置的最小值(word1第i – 1位置和word2第j – 1位置相等则就是f[i – 1][j – 1],不相等则f[i – 1][j – 1] + 1(替换字母))。

参考代码

public class Solution { 
    /** 
     * @param word1 & word2: Two string. 
     * @return: The minimum number of steps. 
     */ 
    public int minDistance(String word1, String word2) { 
        int m = word1.length(); 
        int n = word2.length(); 
        int[][] f = new int[m + 1][n + 1]; 
         
        for (int i = 0; i < m + 1; i++) { 
            f[i][0] = i; 
        } 
         
        for (int j = 0; j < n + 1; j++) { 
            f[0][j] = j; 
        } 
         
        for (int i = 1; i < m + 1; i++) { 
            for (int j = 1; j < n + 1; j++) { 
                // insert, delete 
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1); 
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) { 
                    // no replace 
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);     
                } else { 
                    // replace 
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1); 
                } 
            } 
        } 
         
        return f[m][n]; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表评论

您的电子邮箱地址不会被公开。