怎么做网站的图片,黄页88怎样发信息,不封号的电销系统,muse 转 wordpress主题给定两个字符串s1, s2#xff0c;找到使两个字符串相等所需删除字符的ASCII值的最小和。
示例 1:
输入: s1 “sea”, s2 “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。 在 “eat” 中删除 “t” 并将 116 加入总和。 结束时#xff0…给定两个字符串s1, s2找到使两个字符串相等所需删除字符的ASCII值的最小和。
示例 1:
输入: s1 “sea”, s2 “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。 在 “eat” 中删除 “t” 并将 116 加入总和。 结束时两个字符串相等115 116 231 就是符合条件的最小和。
解题思路
数组含义dp[i][j]代表s1的前i位和s2的前j位使两个字符串相等所需删除字符的ASCII值的最小和 初始化当s1和s2分别为空时另一个字符串需要删除全部字符 状态转移3种情况1.删掉s1的i位 2.删掉s2的j位 3.同时删掉 s1和s2的第ij位 选择最小值
代码
class Solution {public int minimumDeleteSum(String s1, String s2) {int ns1.length(),ms2.length();int [][] dpnew int[n1][m1];for(int i1;in;i)dp[i][0]dp[i-1][0]s1.charAt(i-1);for(int i1;im;i)dp[0][i]dp[0][i-1]s2.charAt(i-1); for(int i1;in;i)for(int j1;jm;j)if(s1.charAt(i-1)s2.charAt(j-1))dp[i][j]dp[i-1][j-1];else dp[i][j] Math.min(dp[i-1][j]s1.charAt(i-1),Math.min(dp[i][j-1] s2.charAt(j-1),dp[i-1][j-1]s1.charAt(i-1)s2.charAt(j-1)));return dp[n][m];}
}
