LWC 55:712. Minimum ASCII Delete Sum for Two Strings

LWC 55:712. Minimum ASCII Delete Sum for Two Strings

传送门:712. Minimum ASCII Delete Sum for Two Strings

Problem:

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = “sea”, s2 = “eat” Output: 231 Explanation: Deleting “s” from “sea” adds the ASCII value of “s” (115) to the sum. Deleting “t” from “eat” adds 116 to the sum. At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = “delete”, s2 = “leet” Output: 403 Explanation: Deleting “dee” from “delete” to turn the string into “let”, adds 100[d]+101[e]+101[e] to the sum. Deleting “e” from “leet” adds 101[e] to the sum. At the end, both strings are equal to “let”, and the answer is 100+101+101+101 = 403. If instead we turned both strings into “lee” or “eet”, we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.

All elements of each string will have an ASCII value in [97, 122].

思路: 动态规划,和最小编辑距离相似,先用递归的方式解一遍,定义f(i, j)表示:字符串(0,i)和字符串(0,j)该问题的解。

目标在于缩小子问题的规模,很简单,如果末尾的i和j对应的元素不相等,则一定删除其中的某个,所以有: f(i, j) = min{f(i - 1, j) + 删除i的代价, f(i, j - 1) + 删除j的代价}

如果相等,则可删除可不删除。 f(i, j) = f(i - 1, j - 1),但既然能不删,则删了岂不是答案更大,所以只要上述递推式即可。

递归+记忆化版本如下:

    public int minimumDeleteSum(String s1, String s2) {
        dp = new int[s1.length() + 1][s2.length() + 1];
        return go(s1.toCharArray(), s2.toCharArray(), s1.length() - 1, s2.length() - 1);
    }

    int[][] dp;
    int go(char[] cs1, char[] cs2, int p1, int p2) {
        if (dp[p1 + 1][p2 + 1] > 0) return dp[p1 + 1][p2 + 1];
        if (p1 == -1 && p2 == -1) return 0;
        if (p1 == -1 && p2 != -1) {
            int ans = go(cs1, cs2, p1, p2 - 1);
            ans += cs2[p2];
            dp[0][p2 + 1] = ans;
            return ans;
        }
        if (p1 != -1 && p2 == -1) {
            int ans = go(cs1, cs2, p1 - 1, p2);
            ans += cs1[p1];
            dp[p1 + 1][0] = ans;
            return ans;
        }

        if (cs1[p1] == cs2[p2]) {
            int ans = go(cs1, cs2, p1 - 1, p2 - 1);
            dp[p1 + 1][p2 + 1] = ans;
            return ans;
        }
        else {
            int a1 = go(cs1, cs2, p1 - 1, p2);
            int a2 = go(cs1, cs2, p1, p2 - 1);
            return dp[p1 + 1][p2 + 1] = Math.min(a1 + cs1[p1], a2 + cs2[p2]);
        }
    }

有了递归版本,咱们来个递推的(动态规划):

    public int minimumDeleteSum(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int n1 = cs1.length;
        int n2 = cs2.length;
        int[][] dp = new int[n1 + 1][n2 + 1];

        for (int i = 0, t = 0; i < n2; ++i) {
            t += cs2[i];
            dp[0][i + 1] = t;
        }

        for (int i = 0, t = 0; i < n1; ++i) {
            t += cs1[i];
            dp[i + 1][0] = t;
        }

        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = Math.min(dp[i][j - 1] + cs2[j - 1], dp[i - 1][j] + cs1[i - 1]);
                }
            }
        }
        return dp[n1][n2];
    }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏偏前端工程师的驿站

CSS魔法堂:小结一下Box Model与Positioning Scheme

前言  对于Box Model和Positioning Scheme中3种定位模式的细节,已经通过以下几篇文章记录了我对其的理解和思考。 《CSS魔法堂:重新...

1646
来自专栏数据小魔方

Stata特别篇(下)——多变量图表汇总!

今天跟大家分享Stata特别篇的下篇——多变量图表汇总! 在多变量图表中,增加的变量仅仅限于定距变量,也可以是定类变量。 打开数据集: use "D:\Sta...

4045
来自专栏海天一树

Codeforces Round #463 C.Permutation Cycle

一、题目 http://codeforces.com/contest/932/problem/C 二、分析 (一)何谓Permutation Cycle 以例1...

31610
来自专栏ml

cf------(round 2)A. Winner

A. Winner time limit per test 1 second memory limit per test 64 megabytes in...

2805
来自专栏刘望舒

几条曲线构建Android表白程序

每年的情人节和七夕,甜蜜与痛苦的日子,做点什么好呢? 写诗画画送礼物,逛街吃饭看电影? 作为搬砖爱好者,写个表白脚本或者动画什么的吧。 想起之前看到的一段H5动...

653
来自专栏ml

HDUOJ-----1074 Integer Inquiry

Integer Inquiry Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

32714
来自专栏猛牛哥的博客

牛牛牌大小计算

1524
来自专栏GIS讲堂

openlayers实现wfs属性查询和空间查询

一直在寻求openlayers中wfs加载和属性查询的相关操作,功夫不负有心人,蓦然回首,那人却在灯火阑珊处,找到了这篇博文:http://blog.csdn....

315
来自专栏ml

HDUOJ----剪花布条

剪花布条 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

34312
来自专栏前端说吧

JS - 兼容到ie7的自定义样式的滚动条封装

774

扫码关注云+社区