编辑距离(一)

[编程题]编辑距离(一)

热度指数：23808 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

1.插入一个字符

2.删除一个字符

3.修改一个字符。

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

示例1

输入

"nowcoder","new"

输出

说明

"nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次
"nowcoder"=>"new"(删除"coder")，删除操作5次

示例2

输入

"intention","execution"

输出

说明

一种方案为:
因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改即可

示例3

输入

"now","nowcoder"

输出

算法知识视频讲解

TypeScript

爱刷美剧的土拨鼠在做ppt

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @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];
}

编辑于 2024-03-15 18:33:10 回复(0)