上海专业网站建设费,做营销型网站公司,徐州的网站设计,台州小型网站建设题目链接 Leetcode.712 两个字符串的最小ASCII删除和 mid 题目描述
给定两个字符串 s1 和 s2#xff0c;返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1: 输入: s1 “sea”, s2 “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加…题目链接 Leetcode.712 两个字符串的最小ASCII删除和 mid 题目描述
给定两个字符串 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 ≤ s 1. l e n g t h , s 2. l e n g t h ≤ 1000 0 \leq s1.length, s2.length \leq 1000 0≤s1.length,s2.length≤1000s1 和 s2 由小写英文字母组成
解法动态规划
我们定义 f ( i , j ) f(i,j) f(i,j) 为使得 s1 的前 i i i 个字符 和 s2 的前 j j j 个字符相等所需要删除字符的最小 ASCII 值。
按照定义最终我们要返回的答案就是 f ( m , n ) f(m,n) f(m,n) m , n m,n m,n 分别为 s1 和 s2 中的字符数量。
我们用 A S C I I ( x ) ASCII(x) ASCII(x) 表示 x x x 的ASCII值。
如果 s 1 [ i − 1 ] s 2 [ j − 1 ] s1[i-1] s2[j-1] s1[i−1]s2[j−1]那么 f ( i , j ) f ( i − 1 , j − 1 ) f(i,j) f(i - 1,j - 1) f(i,j)f(i−1,j−1)如果 s 1 [ i − 1 ] ≠ s 2 [ j − 1 ] s1[i-1] \neq s2[j-1] s1[i−1]s2[j−1]那么既可能选择删除 s 1 [ i − 1 ] s1[i-1] s1[i−1]此时 f ( i , j ) f ( i − 1 , j ) A S C I I ( s 1 [ i − 1 ] ) f(i,j) f(i-1,j) ASCII(s1[i-1]) f(i,j)f(i−1,j)ASCII(s1[i−1])也有可能选择删除 s 2 [ j − 1 ] s2[j-1] s2[j−1]此时 f ( i , j ) f ( i , j − 1 ) A S C I I ( s 2 [ j − 1 ] ) f(i,j) f(i,j - 1) ASCII(s2[j-1]) f(i,j)f(i,j−1)ASCII(s2[j−1])。所以要取二者的最小值即最终式子为 f ( i , j ) m a x { f ( i − 1 , j ) A S C I I ( s 1 [ i − 1 ] ) , f ( i , j − 1 ) A S C I I ( s 2 [ j − 1 ] ) } f(i,j) max \{f(i-1,j) ASCII(s1[i-1]),f(i,j - 1) ASCII(s2[j-1]) \} f(i,j)max{f(i−1,j)ASCII(s1[i−1]),f(i,j−1)ASCII(s2[j−1])}。
对于一些特殊情况我们需要提前处理。对于 f ( i , 0 ) f(i,0) f(i,0) f ( 0 , j ) f(0,j) f(0,j) 我们只能选择删除所有的字符使得 s1 和 s2 都为空。
时间复杂度 O ( n 2 ) O(n^2) O(n2)
C代码
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int m s1.size() , n s2.size();vectorvectorint f(m 1,vectorint(n 1));for(int i 1;i m;i) f[i][0] f[i - 1][0] static_castint(s1[i - 1]);for(int j 1;j n;j) f[0][j] f[0][j - 1] static_castint(s2[j - 1]);for(int i 1;i m;i){for(int j 1;j n;j){if(s1[i - 1] s2[j - 1]) {f[i][j] f[i - 1][j - 1];}else{int a f[i][j - 1] static_castint(s2[j - 1]);int b f[i - 1][j] static_castint(s1[i - 1]);f[i][j] min(a,b);}}}return f[m][n];}
};
