C++で1つの文字列を別の文字列に変換する操作を取得するプログラム

2つの文字列SとTがあるとします。SをTに変更する操作の最短シーケンスを見つける必要があります。ここでの操作は、基本的に文字の削除または挿入のいずれかです。

したがって、入力がS ="xxxy" T ="xxyy"の場合、出力は["x"、 "x"、 "-x"、 "y"、"+y"]になります。これは場所を意味します。最初の2つのx、次に3番目のxを削除し、次にyを配置してから、新しいyを追加します。

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

• サイズ505x505のテーブルdpを作成する
• 関数help（）を定義します。これには、i、j、S、Tが必要です。
• iがSのサイズと同じで、jがTのサイズと同じである場合、-
  • return dp [i、j] =0
• iがSのサイズと同じである場合、-
  • return dp [i、j] =1 + help（i、j + 1、S、T）
• jがTのサイズと同じである場合、-
  • return dp [i、j] =1 + help（i + 1、j、S、T）
• dp [i、j]が-1に等しくない場合、-
  • return 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）
• 挿入：=1 + help（i、j + 1、S、T）
• minVal：=min（{dontDo、del、insert}）
• return dp [i、j] =minVal
• 関数getPath（）を定義します。これには、i、j、S、T、curr、配列retが必要です。
• currが0と同じで、iがSのサイズと同じで、jがTのサイズと同じである場合、-
  • 戻る
• i
• retの最後にstring（1、S [i]）を挿入します
• getPath（i + 1、j + 1、S、T、curr、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, ]