C ++中两个字符串的最小ASCII删除总和

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个单词w1和w2，我们必须找到已删除字符的最低ASCII总和，以使w1和w2相同，其中在每一步中，我们可以删除任一字符串中的一个字符。因此，如果输入像“ sea”和“ eat”，那么输出将为231，因为我们需要从w1中删除“ s”，所以它将是“ ea”，并从w2中从“ eat”中删除“ t”。然后它们是相同的。从“进餐”中删除“ t”会使总和增加116，最后，两个字符串相同，并且115 + 116 = 231是实现此目标的最小总和。

为了解决这个问题，我们将遵循以下步骤-

  • n：= s1的大小，m：= s2的大小

  • 在字符串s1和s2之前添加一个空格，然后相应地更新s1和s2

  • 制作一张大小为（n + 1）x（m + 1）的桌子

  • 对于我：= 1到m

    • dp [0，i]：= dp [0，i-1] + s2 [i]

  • 对于我：= 1到n

    • dp [i，0]：= dp [i – 1，0] + s1 [i]

  • 对于我在1到n范围内

    • 如果s1 [i] = s2 [j]

    • 否则dp [i，j] = dp [i – 1，j] + 1和dp [i，j-1] + 1的最小值

    • dp [i，j]：= dp [i – 1，j-1]

    • 对于1到m范围内的j

    • 返回dp [n，m]

    例子（C ++）

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
    public:
       int minimumDeleteSum(string s1, string s2) {
          int n = s1.size();
          int m = s2.size();
          s1 = " " + s1;
          s2 = " " + s2;
          vector < vector <int> > dp(n + 1, vector <int>(m + 1));
          for(int i = 1; i <= m; i++){
             dp[0][i] = dp[0][i - 1] + s2[i];
          }
          for(int i = 1; i <= n; i++){
             dp[i][0] = dp[i - 1][0] + s1[i];
          }
          for(int i = 1; i <= n; i++){
             for(int j = 1; j <= m; j++){
                if(s1[i] == s2[j]){
                   dp[i][j] = dp[i - 1][j - 1];
                }
                else{
                   dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]);
                }
             }
          }
          return dp[n][m];
       }
    };
    main(){
       Solution ob;
       cout << (ob.minimumDeleteSum("sea", "eat"));
    }

    输入项

    "sea"
    "eat"

    输出结果

    231

    以上是 C ++中两个字符串的最小ASCII删除总和 的全部内容， 来源链接： utcz.com/z/327274.html

    回到顶部