leetcode 712 Minimum ASCII Delete Sum for Two Strings 详细解答

  • 时间:
  • 来源:互联网
  • 文章标签:

leetcode 712 Minimum ASCII Delete Sum for Two Strings 详细解答

在这里插入图片描述
解法1
这个题牵涉到两个数组的一些比较关系,会想到用动态规划求解。
至于怎么求解,这里说的是删到的字母ASCII码之和,这里换个思路可以求两个字符串所有字母的ASCII码之和减去两个字符串相同子序列出现的字母的ASCII码值之和。
所以状态转移方程就是求两个字符串相同序列的和。
F( i+1, j+1 ) 表示字符串 s1[0 … i] 和 s2[0 … j]相同子序列ASCII的和。

F(i+1,j+1)={F(i,j)+2ASCII(s1[i])s1[i]=s2[j]max(F(i,j+1),F(i+1,j))s1[i]!=s2[j] F( i+1, j+1 )=\begin{cases} F( i, j ) + 2*ASCII(s1[i])& s1[i]=s2[j] \\ max(F(i,j+1), F(i+1,j)) & s1 [i] != s2[j] \\ \end{cases}

所以代码如下:
在这里插入图片描述
时间复杂度O(N2), 空间复杂度O(N2)

另一种解法空间复杂度是O(N),思路是一样的。留给大家自己参考:
在这里插入图片描述

本文链接http://www.taodudu.cc/news/show-83130.html