Java实现 LeetCode 72 编辑距离

72. 编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1:

输入: word1 = “horse”, word2 = “ros”

输出: 3

解释:

horse -> rorse (将 ‘h’ 替换为 ‘r’)

rorse -> rose (删除 ‘r’)

rose -> ros (删除 ‘e’)

示例 2:

输入: word1 = “intention”, word2 = “execution”

输出: 5

解释:

intention -> inention (删除 ‘t’)

inention -> enention (将 ‘i’ 替换为 ‘e’)

enention -> exention (将 ‘n’ 替换为 ‘x’)

exention -> exection (将 ‘n’ 替换为 ‘c’)

exection -> execution (插入 ‘u’)

class Solution {

   public int minDistance(String word1, String word2) {

        int len1 = word1.length();

        int len2 = word2.length();

        //处理有空字符串的特殊情况

        if (len1 * len2 == 0)

            return len1 + len2;

        String longerStr = len1 > len2 ? word1 : word2;

        String shorterStr = len1 > len2 ? word2 : word1;

        int shorterOne = Math.min(len1, len2);

        //dp数组长度为两字符串中长度较小的那个

        int[] dp = new int[shorterOne + 1];

        //初始化dp数组

        for (int i = 0; i < shorterOne + 1; i++) {

            dp[i] = i;

        }

        //从长度较长的字符串开始遍历，注意j从1开始，取第j-1位字符，因此结束位置是 longerStr.length()

        for (int j = 1; j <= longerStr.length(); j++) {

            // 每次遍历短字符串前，先给left赋初始值

            int left = j;

            //遍历长度较短的字符串，同样从1开始，取第i-1位字符，因此结束位置是 shortStr.length()

            for (int i = 1; i <= shorterStr.length(); i++) {

                int updateDown = dp[i] + 1;

                int updateLeft = left + 1;

                int updateLeftDown = dp[i - 1];

                //如果当前字符不匹配，左下角的那个值要加一，表示替换当前字符

                if (longerStr.charAt(j - 1) != shorterStr.charAt(i - 1)) {

                    updateLeftDown++;

                }

                //获取较小的那个

                int min = Math.min(updateLeft, Math.min(updateDown, updateLeftDown));

                //因为 dp[i - 1]后面用不到了，替换为当前的left值

                dp[i - 1] = left;

                //如果遍历到最后一个时，直接更新dp[i]

                if(i == dp.length - 1){

                    dp[i] = min;

                }else{

                    //否则更新左边的值，而不是直接更新 dp[i]，因为下个循环需要用到原来的 dp[i]以及刚更新的left

                    left = min;

                }

            }

        }

        return dp[shorterOne];

    }

}

巴特西

Java实现 LeetCode 72 编辑距离

72. 编辑距离

最新文章

热门文章