深圳高端网站建设公司排名,新手怎么优化网站,杭州网页设计公司招聘,郑州网站制作公司汉狮编辑距离
https://leetcode.cn/problems/edit-distance/description/
描述
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最少操作数你可以对一个单词进行如下三种操作#xff1a; 插入一个字符删除一个字符替换一个字符
示例 1
输入 请返回将 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’)
提示
0 word1.length, word2.length 500word1 和 word2 由小写英文字母组成
Typescript 版算法实现 1 ) 方案1: 动态规划
function minDistance(word1: string, word2: string): number {const n word1.length;const m word2.length;// 有一个字符串为空串if (n * m 0) {return n m;}// DP 数组const D: number[][] Array.from({ length: n 1 }, () Array(m 1).fill(0));// 边界状态初始化for (let i 0; i n 1; i) {D[i][0] i;}for (let j 0; j m 1; j) {D[0][j] j;}// 计算所有 DP 值for (let i 1; i n 1; i) {for (let j 1; j m 1; j) {const left D[i - 1][j] 1;const down D[i][j - 1] 1;let left_down D[i - 1][j - 1];if (word1.charAt(i - 1) ! word2.charAt(j - 1)) {left_down 1;}D[i][j] Math.min(left, down, left_down);}}return D[n][m];
}2 ) 方案2: 动态规划自底向上
function minDistance(word1: string, word2: string): number {const n1 word1.length;const n2 word2.length;// 初始化 DP 数组const dp: number[][] Array.from({ length: n1 1 }, () Array(n2 1).fill(0));// 初始化第一行for (let j 1; j n2; j) {dp[0][j] dp[0][j - 1] 1;}// 初始化第一列for (let i 1; i n1; i) {dp[i][0] dp[i - 1][0] 1;}// 计算所有 DP 值for (let i 1; i n1; i) {for (let j 1; j n2; j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 1;}}}return dp[n1][n2];
}
