C++での2つの文字列の最小ASCII削除合計

2つの単語w1とw2があるとすると、w1とw2を同じにするために、削除された文字の最小のASCII合計を見つける必要があります。各ステップで、どちらかで1つの文字を削除できます。ストリング。したがって、入力が「sea」や「eat」の場合、出力は231になります。これは、w1から「s」を削除する必要があるためです。これは「ea」になり、w2の「eat」から「t」を削除します。その後、それらは同じです。 「eat」から「t」を削除すると、合計に116が追加され、最後に両方の文字列が同じになり、115 + 116=231がこれを達成するために可能な最小の合計になります。

これを解決するには、次の手順に従います-

• n：=s1のサイズ、m：=s2のサイズ
• 文字列s1とs2の前に1つの空白スペースを追加し、それに応じてs1とs2を更新します
• サイズ（n + 1）x（m + 1）のテーブルを1つ作成します
• for i：=1からm
  • dp [0、i]：=dp [0、i-1] + s2 [i]
• for i：=1からn
  • dp [i、0]：=dp [i – 1、0] + s1 [i]
• 1からnの範囲のiの場合
  • 1からmの範囲のjの場合
    • if s1 [i] =s2 [j]
      • dp [i、j]：=dp [i – 1、j-1]
    • else dp [i、j]=最小のdp[i – 1、j] +1およびdp[i、j-1] + 1
• return 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