两个字符串的删除操作(非hot100) - Problem Detail - CodeFun2000

1000ms

Difficulty: 5

所属公司 : Hot100

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库面试手撕 LC Hot 100(ACM模式版)，可解锁完整内容。

购买面试手撕 LC Hot 100(ACM模式版) 开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（面试手撕 LC Hot 100(ACM模式版)），可解锁完整内容。

购买题库开通会员

解题思路

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

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

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

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

题目描述

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

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