您的位置: 首页 > 文章 > 力扣小白刷题之583题两个字符串的删除操作 力扣小白刷题之583题两个字符串的删除操作 分类: 文章 • 2023-10-15 23:46:05 题目描述 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。 思路 可以转换为求两个字符串的最长公共子序列问题。 最长公共子序列的状态定义为：dp[i][j] 的含义是：对于 S1[0,…i] 和S2[0,…j]，它们的最长公共子序列的长度为 dp[i][j]； 最长公共子序列的状态转移方程为： 此题 最小步数 = 两个字符串总长度 - 2 * 最长公共子序列长度 代码
