Leetcode 712. 两个字符串的最小ASCII删除和

红太狼 2021-12-17 15:57 212阅读 0赞

题目描述：

https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/

解题思路：

也是典型的dp问题。利用二维dp数组求解。

建立一个二维数组Dp\[ i \]\[ j \]，Dp\[ i \]\[ j \]表示从s1中拿出 i 个元素和从 s2 中拿出 j 个元素的最小删除数。

当s1\[i\]=s2\[j\]时，dp\[i\]\[j\] = dp\[i-1\]\[j-1\].

当s1\[i\]!=s2\[j\]，

动态转移方程为：

dp\[i\]\[j\] = min(dp\[i-1\]\[j\]+s1\[i\], dp\[i\]\[j-1\]+s2\[j\], dp\[i-1\]\[j-1\]+s1\[i\]+s2\[j\]) 。

代码：

class Solution {
    public:
        int minimumDeleteSum(string s1, string s2) {
            int len1 = s1.size();
            int len2 = s2.size();
            vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
            for(int i=1; i<=len1; i++)
            {
                dp[i][0] = dp[i-1][0] + s1[i-1];
            }
            for(int i=1; i<=len2; i++)
            {
                dp[0][i] = dp[0][i-1] + s2[i-1];
            }
            for(int i=0; i<len1; i++)
            {
                for(int j=0; j<len2; j++)
                {
                    if(s1[i] == s2[j])
                        dp[i+1][j+1] = dp[i][j];
                    else
                    {
                        dp[i+1][j+1] = min(dp[i][j+1]+s1[i], dp[i+1][j]+s2[j]);
                        dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+s1[i]+s2[j]);
                    }
                }
    
            }
            return dp[len1][len2];
        }
    };

转载于:https://www.cnblogs.com/LJ-LJ/p/10658873.html

发表评论取消回复

表情：

评论列表（有 0 条评论，212人围观）

还没有评论，来说两句吧...

相关阅读

相关 583. 两个字符串的删除操作 ——【Leetcode每日一题】

583. 两个字符串的删除操作给定两个单词 `word1` 和 `word2` ，返回使得 `word1` 和 `word2` 相同所需的最小步数。每步可以删除任

Love The Way You Lie/ 2024年03月25日 23:12/ 0 赞/ 75 阅读

相关 LeetCode-583. 两个字符串的删除操作

目录题目思路动态规划一动态规划二题目来源 [583. 两个字符串的删除操作][583.] 题目思路两个字符

痛定思痛。/ 2024年03月24日 12:14/ 0 赞/ 48 阅读

相关【算法挨揍日记】day40——712. 两个字符串的最小ASCII删除和、718. 最长重复子数组

712. 两个字符串的最小ASCII删除和 [712. 两个字符串的最小ASCII删除和][712. _ASCII] 题目描述：给定两个字符串`s1` 和 `s

谁践踏了优雅/ 2024年02月05日 14:58/ 0 赞/ 51 阅读

相关 Minimum ASCII Delete Sum for Two Strings（C++两个字符串的最小ASCII删除和）

解题思路： (1)动态规划 class Solution { public: int minimumDeleteSum(string s1,

拼搏现实的明天。/ 2023年01月16日 06:34/ 0 赞/ 116 阅读

相关两个字符串的删除操作

最长公共子序列 package com.bingoabin.algorithm.string; / @Author: xubin34 @Date

Myth丶恋晨/ 2022年09月12日 13:42/ 0 赞/ 250 阅读

相关 712 两个字符串的最小ASCII删除和（最长公共子序列）

1. 问题描述：给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。示例 1: 输入: s1 = "sea", s2 = "eat"

亦凉/ 2022年09月06日 15:28/ 0 赞/ 149 阅读

相关 leetcode-两个不同字符串

找出不同字母 Input: s = "abcd" t = "abcde" Output: e 代码 va

谁借莪１个温暖的怀抱￠/ 2022年06月17日 13:13/ 0 赞/ 280 阅读

相关 LeetCode599. 两个列表的最小索引总和

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果

桃扇骨/ 2022年05月22日 00:13/ 0 赞/ 159 阅读

相关 Leetcode 712. 两个字符串的最小ASCII删除和

题目描述： https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/ 解题

红太狼/ 2021年12月17日 15:57/ 0 赞/ 213 阅读

相关 leetcode 712

这道题的思路：我是根据最长公共子序列的思路得来的。最长公共子序列是： d\[i\]\[j\]表示字符串s1前i个（0～i-1）字符，和字符串s2前j个（0～j-1）字符的最

野性酷女/ 2021年09月29日 04:46/ 0 赞/ 260 阅读