0712. Minimum ASCII Delete Sum for Two Strings

题目信息

题号:

0712

难度:

Medium

主题:

字符串、删除代价、动态规划

原题:

LeetCode 0712

重点:

可从两个字符串任意删除字符,目标是使剩余字符串完全相同;代价按所有被删字符的 ASCII 值累加并取最小值

题目重述

给定两个仅由小写英文字母组成的字符串 s1 和 s2。你可以从任一字符串中删除任意字符,使两个字符串最终变得完全相同。每删除一个字符,就产生等于该字符 ASCII 值的代价。

返回完成上述目标所需的最小删除代价总和。代价需要同时统计从 s1 和 s2 中删除的所有字符;保留下来的字符必须维持各自在原字符串中的相对顺序。两个字符串的长度均在 [1, 1000] 范围内。

自建示例

只需从一个字符串删除字符:

输入:s1 = "abc", s2 = "ac"
输出:98
解释:从 s1 删除字符 'b' 后,两个字符串都变为 "ac";'b' 的 ASCII 值是 98,这是最小总代价。

选择代价更低的共同结果:

输入:s1 = "az", s2 = "za"
输出:194
解释:保留字符 'z',分别从两个字符串删除 'a',总代价为 97 + 97 = 194。若保留 'a',需要删除两个 'z',代价为 122 + 122 = 244,因此不是最优结果。

两个字符串已经完全相同:

输入:s1 = "code", s2 = "code"
输出:0
解释:允许不删除任何字符。两个输入原本就相同,因此删除代价的最小值为 0。