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

相关文章

来自专栏DHUtoBUAA

《剑指Offer》附加题_用两个队列实现一个栈_C++版

  在《剑指Offer》中,在栈和队列习题中,作者留下来一道题目供读者自己实现,即“用两个队列实现一个栈”。   在计算机数据结构中,栈的特点是后进先出,即最后...

32450
来自专栏web前端教室

重学javascript 红皮高程(4)

继续啊,顺着JS高程的目录往下走,今天是3.4.4 Boolean类型。 这个Boolean一般来说它只有二个值,true和false。但其实它还有第三种值, ...

23890
来自专栏高性能服务器开发

(四)sds字符串

今天分析的是Redis源码中的字符串操作类的代码实现。有了上几次的分析经验,渐渐觉得我得换一种分析的方法,如果每个API都进行代码分析,有些功能性的重复,导致分...

415100
来自专栏武培轩的专栏

Leetcode#500. Keyboard Row(键盘行)

给定一个单词列表,只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

19530
来自专栏Golang语言社区

Golang语言断言

golang中的所有程序都实现了interface{}的接口,这意味着,所有的类型如string,int,int64甚至是自定义的struct类型都就此拥有了i...

325110
来自专栏乐享123

Python编程实战 - 笔记1

20290
来自专栏一枝花算不算浪漫

一道笔试题来理顺Java中的值传递和引用传递

11810
来自专栏写代码的海盗

scala如何解决类型强转问题

scala如何解决类型强转问题   scala属于强类型语言,在指定变量类型时必须确定数据类型,即便scala拥有引以为傲的隐式推到,这某些场合也有些有心无力。...

36290
来自专栏函数式编程语言及工具

泛函编程(25)-泛函数据类型-Monad-Applicative

    上两期我们讨论了Monad。我们说Monad是个最有概括性(抽象性)的泛函数据类型,它可以覆盖绝大多数数据类型。任何数据类型只要能实现flatMap+u...

25690
来自专栏我是攻城师

理解BitMap算法的原理

位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有...

17630

扫码关注云+社区

领取腾讯云代金券