厦门做公司网站,广州番禺核酸检测点,东纺服装人才网,工程造价招聘网最新招聘给定两个字符串s1 和 s2#xff0c;返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1: 输入: s1 “sea”, s2 “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。 在 “eat” 中删除 “t” 并将 116 加入总和。 结束时…给定两个字符串s1 和 s2返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1: 输入: s1 “sea”, s2 “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。 在 “eat” 中删除 “t” 并将 116 加入总和。 结束时两个字符串相等115 116 231 就是符合条件的最小和。
示例 2: 输入: s1 “delete”, s2 “leet” 输出: 403 解释: 在 “delete” 中删除 “dee” 字符串变成 “let” 将 100[d]101[e]101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。 结束时两个字符串都等于 “let”结果即为 100101101101 403 。 如果改为将两个字符串转换为 “lee” 或 “eet”我们会得到 433 或 417 的结果比答案更大。
提示: 0 s1.length, s2.length 1000 s1 和 s2 由小写英文字母组成
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m s1.length(), n s2.length();vectorvectorint dp(m1,vectorint(n1));for(int i 1; i m; i){char c1 s1.at(i-1);for(int j 1; j n; j){char c2 s2.at(j-1);if(c1 c2){dp[i][j] dp[i-1][j-1] int(c2);}else{dp[i][j] max(dp[i-1][j], dp[i][j-1]);}}}int ans1 0, ans2 0;for(int i 0; i m; i){ans1 int(s1[i]);}for(int i 0; i n; i){ans2 int(s2[i]);}return ans1 ans2 - 2*dp[m][n];}
};力扣1143的LCS模板题的变形我们采用一样的动态规划进行修改 dp[i][j] dp[i-1][j-1] int(c2);在这行代码中我们将原本的1改成了加上字符的ascII码所以最后dp中储存的是最长公共子序列的ascII码值总和。最后我们计算出字符串s1和s2的ascII码之和然后减去保留下来的相同子序列的ascII码值需要乘以2剩下的就是两个字符串的最小ASCII删除和。
