मान लीजिए कि हमारे पास दो शब्द S और T हैं, तो हमें S से T में बदलने के लिए आवश्यक न्यूनतम संक्रियाओं की संख्या ज्ञात करनी होगी। ऑपरेशन तीन प्रकार के हो सकते हैं, ये हैं
- एक चरित्र डालें,
- एक चरित्र हटाएं
- एक चरित्र बदलें।
इसलिए यदि इनपुट स्ट्रिंग्स "मूल्यांकन" और "उतार-चढ़ाव" हैं, तो परिणाम 5 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=s का आकार, m :=t का आकार,
-
n + 1
आकार का एक सरणी dp बनाएँ -
मेरे लिए 0 से n की सीमा में
-
dp[i] :=आकार की नई सरणी m + 1
-
j के लिए 0 से m की सीमा में:
-
डीपी [आई, जे]:=0
-
अगर मैं =0, तो डीपी [i, जे] =जे
-
अन्यथा जब j =0, तब dp[i, j] :=i
-
-
-
s:=रिक्त स्थान और संयोजन s, t:=रिक्त स्थान और संयोजन t
-
मैं के लिए 1 से n की सीमा में
-
j के लिए 1 से m की सीमा में
-
यदि 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]
-
-
-
वापसी डीपी [एन, एम]
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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
