✔[72]编辑距离

亦凉 2021-06-22 15:38 453阅读 0赞

//给你两个单词 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’)  
//  
// Related Topics 字符串 动态规划

*  动态规划
 *  状态定义：设dp\[i\]\[j\]，i表示单词1所在的字符位，j表示单词2所在的字符位.  
    // dp\[i\]\[j\]表示word1的前i个字符转换到word2前j个字符的最少步数
 *  递推方程：dp\[i\]\[j\]  
    if word1\[i\] == word2\[j\] -> dp\[i\]\[j\] == dp\[i-1\]\[j-1\]  
    if word1\[i\] != word2\[j\] -> dp\[i\]\[j\] == Min \{dp\[i-1\]\[j\]，dp\[i\]\[j-1\]，dp\[i-1\]\[j-1\]\} + 1 为word1插入一个，删除一个，替换一个所需步数的最小值再+1
 *  最终结果在 dp\[word1Len\]\[word2Len\]  
    //算法复杂度 O(n^2)

class Solution { 
    	public int minDistance(String word1, String word2) { 
    		//非空判断
    		if ((word1 == null && word2 == null) || (word1.length() == 0 && word2.length() == 0)) { 
    			return 0;
    		}
    		int word1Len = word1.length();
    		int word2Len = word2.length();
    		char[] word1Arr = word1.toCharArray();
    		char[] word2Arr = word2.toCharArray();
    		//定义二维数组
    		int[][] dp = new int[word1Len + 1][word2Len + 1];
    		//当word1为空字符串，或word2位空字符串赋初值
    		for (int j = 0; j <= word2Len; j++) { 
    			dp[0][j] = j;
    		}
    		for (int i = 0; i <= word1Len; i++) { 
    			dp[i][0] = i;
    		}
    		//执行递推方程
    		for (int i = 1; i <= word1Len; i++) { 
    			for (int j = 1; j <= word2Len; j++) { 
    				if (word1Arr[i] == word2Arr[j]) { 
    					dp[i][j] = dp[i - 1][j - 1];
    				} else { 
    					dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
    				}
    			}
    		}
    		return dp[word1Len][word2Len];
    	}
    }