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

C++에서 두 문자열 사이의 최소 편집 거리를 찾는 프로그램

<시간/>

S와 T라는 두 단어가 있다고 가정하고 S에서 T로 변환하는 데 필요한 최소 연산 수를 찾아야 합니다. 연산에는 세 가지 유형이 있습니다.

  • 문자 삽입,
  • 캐릭터 삭제
  • 문자를 교체합니다.

따라서 입력 문자열이 "evaluate" 및 "fluctuate"이면 결과는 5가 됩니다.

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

  • n :=s의 크기, m :=t의 크기,

  • n + 1 크기의 배열 dp 생성

  • 범위 0에서 n까지의 i에 대해

    • dp[i] :=m + 1 크기의 새 배열

    • 0에서 m 사이의 j에 대해:

      • dp[i, j] :=0

      • i =0이면 dp[i,j] =j

      • 그렇지 않으면 j =0일 때 dp[i, j] :=i

  • s :=공백 및 s 연결, t :=공백 및 t 연결

  • 범위 1에서 n까지의 i에 대해

    • 범위 1에서 m까지의 j에 대해

      • s[i]가 t[j]가 아니면 dp[i, j] :=1 + min of dp[i – 1, j], dp[i, j - 1], dp[i – 1, j – 1]

      • 그렇지 않으면 dp[i, j] :=dp[i – 1, j – 1]

  • 반환 dp[n, m]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minDistance(string s, string t) {
      int n = s.size();
      int m =t.size();
      int** dp = new int*[n+1];
      for(int i =0;i<=n;i++){
         dp[i] = new int[m+1];
         for(int j=0;j<=m;j++){
            dp[i][j]=0;
            if(i==0)dp[i][j]=j;
            else if(j==0)dp[i][j] = i;
         }
      }
      s = " " + s;
      t = " " + t;
      for(int i =1;i<=n;i++){
         for(int j = 1;j<=m;j++){
            if(s[i] !=t[j]){
               dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
            }else{
               dp[i][j] = dp[i-1][j-1];
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.minDistance("fluctuate", "evaluate"));
}

입력

"fluctuate"
"evaluate"

출력

5