本文共 1038 字，大约阅读时间需要 3 分钟。

给你两个单词 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’)

解题思路：总共可分为3个操作，对A插入一个字符；对A删除一个字符(即对B插入一个字符操作相等)；对A替换一个字符；当前字符的操作取决于前一个字符；

对于插入操作而言，要不就是i-1要不就是j-1；而替换操作，可能当前字符相等，无需再次替换；也可能当前字符不等，需尝试一下替换。

动态规划的思路进行解题。

package com.lcz.leetcode;// 编辑距离import java.util.*;public class Leetcode72 {
   	class Solution {
   	    public int minDistance(String word1, String word2) {
   	    	// 动态规划来解题	    	// 判断输入	    	int len1 = word1.length();	    	int len2 = word2.length();	    	if(len1*len2==0) {
   	    		//有一个为空串	    		return Math.max(len1, len2);	    	}	    		    	// 动态规划	    	int[][] dp = new int[len1+1][len2+1];	    	// 初始化赋值	    	for(int i=0;i

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111856230 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！