解题思路

本题可以转化为求两个字符串的最长公共子序列，即 $LCS$。

如果 $word1$ 和 $word2$ 的最长公共子序列长度为 $lcs$，那么：

• $word1$ 需要删除 $word1.length - lcs$ 个字符
• $word2$ 需要删除 $word2.length - lcs$ 个字符

Leetcode 583.两个字符串的删除操作

题目描述

给定两个单词 $word1$ 和 $word2$。

每步可以删除任意一个字符串中的一个字符。

请返回使得 $word1$ 和 $word2$ 相同所需的最少步数。

输入描述

第一行输入一个字符串 $word1$。

第二行输入一个字符串 $word2$。

输出描述

输出一个整数，表示使 $word1$ 和 $word2$ 相同所需的最少删除步数。

样例 $1$

输入

sea
eat

输出

2

样例解释

第一步将 $word1$ 中的 $sea$ 删除字符 $s$，变为 $ea$。

第二步将 $word2$ 中的 $eat$ 删除字符 $t$，变为 $ea$。

因此最少需要 $2$ 步。

样例 $2$

输入

leetcode
etco

输出

4

数据范围

$1 <= word1.length, word2.length <= 500$

$word1$ 和 $word2$ 只包含小写英文字母。