给定两个字符串 str1 和 str2 ,请你算出将 str1 转为 str2 的最少操作数。
你可以对字符串进行3种操作:
1.插入一个字符
2.删除一个字符
3.修改一个字符。
字符串长度满足 ,保证字符串中只出现小写英文字母。
"nowcoder","new"
6
"nowcoder"=>"newcoder"(将'o'替换为'e'),修改操作1次 "nowcoder"=>"new"(删除"coder"),删除操作5次
"intention","execution"
5
一种方案为: 因为2个长度都是9,后面的4个后缀的长度都为"tion",于是从"inten"到"execu"逐个修改即可
"now","nowcoder"
5
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str1 string字符串 * @param str2 string字符串 * @return int整型 */ export function editDistance(str1: string, str2: string): number { // write code here const m = str1.length; const n = str2.length; // 初始化 dp 数组 const dp: number[][] = new Array(m + 1); for (let i = 0; i <= m; i++) { dp[i] = new Array(n + 1).fill(0); } // 初始化边界条件 for (let i = 0; i <= m; i++) { dp[i][0] = i; } for (let j = 0; j <= n; j++) { dp[0][j] = j; } // 动态规划计算最少操作数 for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (str1.charAt(i - 1) === str2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = Math.min( dp[i - 1][j - 1] + 1, // 修改字符 Math.min( dp[i][j - 1] + 1, // 插入一个字符 dp[i - 1][j] + 1 ) ); // 删除一个字符 } } } return dp[m][n]; }