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 条评论
登录 后参与评论

相关文章

来自专栏恰同学骚年

正则表达式30分钟入门教程--deerchao

原文地址:http://www.cnblogs.com/deerchao/archive/2006/08/24/zhengzhe30fengzhongjiaoc...

1124
来自专栏我的博客

正则表达式–应用篇

匹配年月日(常见三种格式2012-12-12、2012/12/12、2012年12月12日) <?php //匹配格式如:2012年12月12日 $mode...

2473
来自专栏伪君子的梦呓

华氏温度转摄氏温度~ C++ 做法

题目链接:http://www.dotcpp.com/oj/problem1005.html

883
来自专栏积累沉淀

Linux之grep和egrep命令总结

grep / egrep 语法: grep  [-cinvABC]  'word'  filename -c :打印符合要求的行数 -i :忽略大小写 ...

16810
来自专栏前端杂货铺

URI编码解码和base64

概述 对于uri的编解码,在js中有3对函数,分别是escape/unescape,encodeURI/decodeURI,encodeURIComponent...

2787
来自专栏jouypub

Linux命令之awk

awk '{cmd="rm "$0;system(cmd)}' filename.txt

1064
来自专栏小樱的经验随笔

Codeforces 706B Interesting drink

B. Interesting drink time limit per test:2 seconds memory limit per test:256 meg...

2758
来自专栏数据结构与算法

P3369 【模板】普通平衡树(Treap/SBT)

题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询...

2738
来自专栏技术碎碎念

LeetCode-62-Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

2995
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

3428

扫码关注云+社区