word1과 word2라는 두 단어가 있다고 가정하면 word1에서 word2까지 합치기 위해 필요한 최소 연산 수를 찾아야 합니다. 작업은 문자 삽입, 문자 삭제 및 문자 바꾸기의 세 가지 유형이 있습니다. 따라서 입력 문자열이 "evaluate" 및 "fluctuate"이면 결과는 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=w1의 크기, m :=w2의 크기,
-
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
-
-
-
w1 :=공백 및 연결 w1, w2 :=공백 및 연결 w2
-
범위 1에서 n까지의 i에 대해
-
범위 1에서 m까지의 j에 대해
-
w1[i]가 w2[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 w1, string w2) {
int n = w1.size();
int m =w2.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;
}
}
w1 = " " + w1;
w2 = " " + w2;
for(int i =1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(w1[i] !=w2[j]){
dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i1][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