编辑距离的最少操作数动态规划解法

题目链接：https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da

题目描述

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。

你可以对字符串进行3种操作：

1.插入一个字符

2.删除一个字符

3.修改一个字符。

字符串长度满足 1≤n≤1000 ，保证字符串中只出现小写英文字母。

示例 1：

输入：   "nowcoder","new"
返回值： 6
说明：   "nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次
        "nowcoder"=>"new"(删除"coder")，删除操作5次

示例 2：

输入：   "intention","execution"
返回值： 5
说明：   一种方案为:
        因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改即可

示例 3：

输入：   "now","nowcoder"
返回值： 5

解题代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        int[][] dp = new int[2][str2.length() + 1]; //定义动规数组，两行分别表示当前和上一轮的结果，分别为i%2和(i+1)%2

        for (int i = 1; i <= str2.length(); i++) { //初始化
            dp[0][i] = i;
        }
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) { //第一种情况
                    if (j - 1 == 0) {
                        dp[i % 2][j] = i - 1;
                    } else {
                        dp[i % 2][j] = dp[(i + 1) % 2][j - 1];
                    }

                } else { //第二种情况
                    if (j - 1 == 0) {
                        dp[i % 2][j] = Math.min(dp[(i + 1) % 2][j] + 1, i);
                    } else {
                        dp[i % 2][j] = Math.min(dp[(i + 1) % 2][j] + 1,
                                                Math.min(dp[(i + 1) % 2][j - 1] + 1, dp[i % 2][j - 1] + 1));
                    }

                }
            }
        }
        return dp[str1.length() % 2][str2.length()];
    }
}