测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7016. 单词的最小修改

编程题 普及/提高-

题目描述

给定两个单词 $S_1$ 和 $S_2$。

你希望通过删除操作,让这两个单词变得一模一样。
每一步操作,你可以从任意一个单词中**删除一个字符**。

请问,最少需要多少步操作,才能让 $S_1$ 和 $S_2$ 变得完全相同?

输入格式

第一行包含一个字符串 $S_1$。
第二行包含一个字符串 $S_2$。

输出格式

输出一个整数,表示最少需要的删除步数。

输入输出样例

输入 #1
sea eat
输出 #1
2
输入 #2
leetcode etco
输出 #2
4

说明/提示

## 样例解释与数据范围

### 样例 #1 解释
- 单词 1:sea $\to$ 删除 s $\to$ ea
- 单词 2:eat $\to$ 删除 t $\to$ ea
- 最终两个单词都变成了 ea
- 总共进行了 2 步删除操作(每个单词各删除了 1 个字符)。

### 样例 #2 解释
- leetcode 删除 l, e, d, e 变成 etco
- etco 不需要删除。
- 总步数为 4。

### 数据范围

- 对于 $100\%$ 的数据,保证字符串仅包含小写英文字母。
- $1 \le \text{字符串长度} \le 500$。

**数据点分布:**
- 测试点 1-5:字符串长度 $\le 10$ (适合手算模拟)
- 测试点 6-15:字符串长度 $\le 100$
- 测试点 16-25:字符串长度 $\le 500$
上一题 去做题 下一题