C++で2つの文字列を一致させるための最小ASCII削除合計を求める方法

問題概要

2つの文字列 w1 と w2 が与えられます。各ステップでどちらかの文字列から1文字を削除することができ、2つの文字列を一致させるために必要な「削除した文字のASCII値の合計」の最小値を求めるのが目標です。

例えば、入力が "sea" と "eat" の場合、出力は 231 になります。これは、w1 から 's'(ASCII値:115)を削除して "ea" とし、w2 の "eat" から 't'(ASCII値:116)を削除すると、両方の文字列が "ea" となって一致するためです。このときの合計は 115 + 116 = 231 となり、これが実現可能な最小値です。

解法の考え方

この問題は動的計画法(DP)を使って効率的に解くことができます。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[0][i] と dp[i][0] には対応する文字のASCII値を累積していきます。

アルゴリズムの手順

• n := s1 の長さ、m := s2 の長さとします
• s1 と s2 の先頭に空白を1つ追加し、インデックスを1始まりにします
• (n + 1) × (m + 1) のサイズのDPテーブルを作成します
• i を 1 から m まで繰り返し:dp[0][i] := dp[0][i-1] + s2[i]
• i を 1 から n まで繰り返し:dp[i][0] := dp[i-1][0] + s1[i]
• i を 1 から n まで、j を 1 から m まで繰り返し:
  • s1[i] == s2[j] なら dp[i][j] := dp[i-1][j-1]
  • そうでなければ dp[i][j] := min(dp[i-1][j] + s1[i], dp[i][j-1] + s2[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

計算量

時間計算量は O(n × m)、空間計算量も O(n × m) です。ここで n と m はそれぞれ s1 と s2 の長さを表します。