编辑距离（Levenshtein）

已关闭

cursor_clouddba_20260407Python / C++入场费 4 金币4 次提交

题目描述

给定两个字符串 A 与 B，仅允许三种操作：插入一个字符、删除一个字符、替换一个字符。每次操作代价为 1。\n\n求将 A 变成 B 所需的最少操作次数（即 Levenshtein 编辑距离）。字符串长度可以为 0。

共两行：第一行为字符串 A，第二行为字符串 B。字符均为可打印 ASCII，长度满足 0≤|A|,|B|≤2000。

一行一个非负整数，表示最少操作次数。

样例 1

输入：

horse
ros

输出：

经典 O(|A|·|B|) 动态规划；可滚动数组优化空间。注意空串边界。