Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 한 문자열을 다른 문자열로 변환하는 작업을 가져오는 프로그램

<시간/>

두 개의 문자열 S와 T가 있다고 가정합니다. S를 T로 변경하는 가장 짧은 연산 시퀀스를 찾아야 합니다. 여기서 연산은 기본적으로 문자를 삭제하거나 삽입하는 것입니다.

따라서 입력이 S ="xxxy" T ="xxyy"와 같으면 출력은 ["x", "x", "-x", "y", "+y"]가 됩니다. 이는 장소를 의미합니다. 처음 두 개의 x를 제거한 다음 세 번째 x를 제거한 다음 y를 배치한 다음 새 y를 추가합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 505 x 505 크기의 테이블 dp 만들기
  • help() 함수를 정의하면 i, j, S, T가 필요합니다.
  • i가 S의 크기와 같고 j가 T의 크기와 같으면 -
    • dp[i, j] =0을 반환
  • i가 S의 크기와 같으면 -
    • dp[i, j] =1 + help(i, j + 1, S, T)를 반환
  • j가 T의 크기와 같으면 -
    • dp[i, j] 반환 =1 + help(i + 1, j, S, T)
  • dp[i, j]가 -1과 같지 않으면 -
    • dp[i, j]를 반환
  • dontDo :=1e5, del :=0, 삽입 :=0
  • S[i]가 T[j]와 같으면 -
    • 하지 마십시오 :=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})
  • 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)
  • 그렇지 않고 dp[i + 1, j] + 1이 curr과 같을 때 -
    • ret 끝에 ("-" 연결 문자열(1, S[i])) 삽입
    • getPath(i + 1, j, S, T, curr - 1, ret)
  • 그렇지 않으면
    • ret 끝에 ("+" 연결 문자열(1, T[j])) 삽입
    • getPath(i, j + 1, S, T, curr - 1, ret)
  • 메인 방법에서 다음을 수행하십시오 -
  • dp를 -1로 채우기
  • ret 배열 정의
  • x :=help(0, 0, S, T)
  • getPath(0, 0, S, T, x, 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, ]