C++で1つの文字列を別の文字列へ変換する最短操作列を求めるプログラム

問題の概要

2つの文字列 S と T が与えられます。S を T に変換するための最短の操作列を見つける必要があります。ここで使用できる操作は、基本的に「1文字の削除」または「1文字の挿入」のいずれかです。

例えば、入力が S = "xxxy"、T = "xxyy" の場合、出力は ["x", "x", "-x", "y", "+y"] となります。これは「最初の2つの x をそのまま配置し、3番目の x を削除(-x)、その後 y を配置し、最後に新しい y を挿入(+y)する」ことを意味します。

解法のアプローチ

この問題は動的計画法(DP)を用いて効率的に解くことができます。メモ化により計算量を抑えつつ、DPテーブルを逆にたどることで実際の操作列を復元します。以下の手順に従って解いていきます。

1. help() 関数:最小操作回数を求める

関数 help(i, j, S, T) を定義します。これは、S の i 番目以降と T の j 番目以降を一致させるために必要な最小操作回数を返します。

• i が S のサイズと一致し、かつ j が T のサイズと一致する場合:
  dp[i][j] = 0 を返します(両方の文字列を使い切ったため、操作は不要)
• i が S のサイズと一致する場合:
  dp[i][j] = 1 + help(i, j + 1, S, T) を返します(T の残りの文字を挿入する必要があります)
• j が T のサイズと一致する場合:
  dp[i][j] = 1 + help(i + 1, j, S, T) を返します(S の残りの文字を削除する必要があります)
• dp[i][j] が -1 以外の場合:
  すでに計算済みのため、dp[i][j] をそのまま返します(メモ化)
• dontDo := 1e5、del := 0、insert := 0 で初期化します
• S[i] が T[j] と一致する場合:
  dontDo := help(i + 1, j + 1, S, T)(文字をそのまま使う場合)
• del := 1 + help(i + 1, j, S, T)(S[i] を削除する場合)
• insert := 1 + help(i, j + 1, S, T)(T[j] を挿入する場合)
• minVal := min({dontDo, del, insert}) を計算します
• dp[i][j] = minVal を返します

2. getPath() 関数:実際の操作列を復元する

関数 getPath(i, j, S, T, curr, ret) を定義します。DPテーブルをたどりながら、実際の操作列を配列 ret に記録していきます。

• curr が 0 で、かつ i が S のサイズ、j が T のサイズと一致する場合:
  処理を終了して return します
• i < S のサイズ、かつ j < T のサイズ、かつ S[i] == T[j]、かつ dp[i + 1][j + 1] == curr の場合:
  ret の末尾に文字 S[i] を追加し、getPath(i + 1, j + 1, S, T, curr, ret) を呼び出します
• そうでなく、dp[i + 1][j] + 1 == curr の場合:
  ret の末尾に "-S[i]" を追加し、getPath(i + 1, j, S, T, curr - 1, ret) を呼び出します(削除操作)
• それ以外の場合:
  ret の末尾に "+T[j]" を追加し、getPath(i, j + 1, S, T, curr - 1, ret) を呼び出します(挿入操作)

3. メイン処理

• dp テーブル全体を -1 で初期化します
• 結果を格納する配列 ret を定義します
• x := help(0, 0, S, T) で最小操作回数を求めます
• getPath(0, 0, S, T, x, ret) で操作列を復元します
• ret を返します

C++ での実装例

より理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v) {
   cout << "[";
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}
int dp[505][505];
class Solution {
   public:
   int help(int i, int j, string& S, string& T) {
      if (i == S.size() && j == T.size())
         return dp[i][j] = 0;
      if (i == S.size())
         return dp[i][j] = 1 + help(i, j + 1, S, T);
      if (j == T.size())
         return dp[i][j] = 1 + help(i + 1, j, S, T);
      if (dp[i][j] != -1)
         return dp[i][j];
      int dontDo = 1e5;
      int del = 0;
      int insert = 0;
      if (S[i] == T[j])
         dontDo = help(i + 1, j + 1, S, T);
      del = 1 + help(i + 1, j, S, T);
      insert = 1 + help(i, j + 1, S, T);
      int minVal = min({dontDo, del, insert});
      return dp[i][j] = minVal;
   }
   void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
      if (curr == 0 && i == S.size() && j == T.size())
         return;
      if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i + 1][j + 1] == curr) {
         ret.push_back(string(1, S[i]));
         getPath(i + 1, j + 1, S, T, curr, ret);
      }else if (dp[i + 1][j] + 1 == curr) {
         ret.push_back("-" + string(1, S[i]));
         getPath(i + 1, j, S, T, curr - 1, ret);
      }else {
         ret.push_back("+" + string(1, T[j]));
         getPath(i, j + 1, S, T, curr - 1, ret);
      }
   }  
   vector<string> solve(string S, string T) {
      memset(dp, -1, sizeof dp);
      vector<string> ret;
      int x = help(0, 0, S, T);
      getPath(0, 0, S, T, x, ret);
      return ret;
   }
};
vector<string> solve(string source, string target) {
   return (new Solution())->solve(source, target);
}
main(){
   string S = "xxxy", T = "xxyy";
   print_vector(solve(S, T));
}

入力

"xxxy", "xxyy"

出力

[x, x, -x, y, +y]

出力の解釈

この出力は、文字をそのまま使う操作をその文字のみで表し、削除は「-文字」、挿入は「+文字」で表しています。つまり、x と x をそのまま残し、3番目の x を削除し、y をそのまま残して、最後に新しい y を挿入することで、S = "xxxy" が T = "xxyy" に変換されます。合計操作回数は2回(削除1回・挿入1回)となり、これが最短の操作列です。