解题思路
本题可以转化为求两个字符串的最长公共子序列，即 LCS。
如果 word1 和 word2 的最长公共子序列长度为 lcs，那么：
- word1 需要删除 word1.length−lcs 个字符
- word2 需要删除 word2.length−lcs 个字符
P4903.两个字符串的删除操作(非hot100)
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 只包含小写英文字母。
